常见的内部排序方法可以分为6大类，具体有10 种：

内部排序

直接选择排序

直接选择排序的思路很简单，第 1 趟比较，把记录定位到第 1 个数据上，拿第 1 个数据依次和它后面每个数据进行比较，如果第 1 个数据大于后面某个数据，变换它们。第 1 趟结束后最小的数据被排在第1 位。同理可得，经过 n-1 趟比较后，完成排序。

public static void selectSort(int[] data)
{
	for (int i = 0; i < data.length-1; i++) 
	{
		for (int j = i+1; j < data.length; j++) 
		{
			if (data[i]>data[j]) 
			{
				int temp=data[i];
				data[i]=data[j];
				data[j]=temp;
			}
		}
	}
}

堆积排序

堆积是一种特殊的二叉树，可分为最大堆积树和最小堆积树。

大堆积树满足3个条件：它是一个完全二叉树；所有节点的值都大于或等于它左右子节点的值；树根是堆积树中最大的。
小堆积树满足3个条件：它是一个完全二叉树；所有节点的值都小于或等于它左右子节点的值；树根是堆积树中最小的。

可以发现，小顶堆的任意子树也是小顶堆，大顶堆的任意子树也是大顶堆。

对于一颗顺序结构的完全二叉树而言，

索引为 k 的节点，它的两个子节点的索引分别为 2k+1、2k+2；

反过来对于索引为 k 的节点，其父节点的索引为 (k-1)/2

堆排序如下步骤进行：

第 1 趟将索引 0 ~ n-1 的全部数据建成大顶堆，就可以选择出树根作为这组数据的最大值。将这一趟所建的大顶堆的根节点与这组数据的最后一个节点交换，就使得这组数据中最大值排在最后。
第 2 趟将索引 0 ~ n-2 的全部数据建成大顶堆，选出这组数据中的最大值。再将这一趟所得的根节点与这组数据的倒数第 2 个节点交换，就使得这组数据中最大值排在倒数第 2 位。
第 k 趟将索引 0 ~ n-k 的全部数据建成大顶堆，选出这组数据中的最大值。再将这一趟所得的根节点与这组数据的倒数第 k 个节点交换，就使得这组数据中最大值排在倒数第 k 位。

由此可见，堆排序的步骤就是重复执行两步：建堆；拿堆的根节点和最后一个节点交换。对于包含 n 个数据的数组而言，堆排序需要经过 n-1 次建堆，每次建堆的作用就是选出该堆的最大值(或最小值)。

建堆从最后一个非终端节点开始即可，因为只需要保证每个非终端节点的值大于等于其子节点的值。

如何建立堆积树

以数据 9,79,46,30,58,49 为例，说明对其建堆的过程：

先将其转换为完全二叉树。
完全二叉树的最后一个非终端节点，也就是最后一个节点的父节点。最后一个节点的索引为 len-1，那么最后一个非终端节点的索引为 (len-2)/2。也就是从索引为 (len-2)/2 的节点开始，如果其子节点的值大于它本身的值，则把它和较大子节点进行交换。
不断向前处理前一个节点，若存在其子节点大于其值，则交换。
如果某个节点和它的某个子节点交换后，该子节点又有子节点，系统还需要再对该子节点进行判断是否进行交换。必须保证父节点的值永远大于其子节点。

/**
 * 堆积排序
 * n 个元素，执行 n-1 次建堆，每次建堆完成后得到最大值
 *
 * @param origin 原始数组
 */
public static void heapSort(int[] origin)
{
  int arraySize = origin.length;
  for (int i = 0; i < arraySize - 1; i++)
  {
    //建堆，大顶堆
    buildMaxHeap(origin, arraySize - 1 - i);
    //交换堆顶和最后一个元素
    swap(origin, 0, arraySize - 1 - i);
  }
}
  
//对 origin 数组从 0 到 lastIndex 建立大顶堆
private static void buildMaxHeap(int[] data, int lastIndex)
{
  //从 lastIndex 处节点(最后一个节点)的父节点开始
  for (int i = (lastIndex - 1) / 2; i >= 0; i--)
  {
    //k 保存当前正在判断的节点的索引
    int k = i;
    //如果当前 k 节点的子节点存在
    while (k * 2 + 1 <= lastIndex)
    {
      //k 节点的左节点的索引
      int biggerNodeIndex = 2 * k + 1;
      //如果 biggerNodeIndex 小于 lastIndex，即 biggerNodeIndex+1 代表的 k 节点的右子节点存在
      if (biggerNodeIndex < lastIndex)
      {
        //如果右子节点的值较大
        if (data[biggerNodeIndex] < data[biggerNodeIndex + 1])
        {
          //biggerNodeIndex 总是记录较大子节点的索引
          biggerNodeIndex++;
        }
      }
      //如果 k 节点的值小于其较大子节点的值
      if (data[k] < data[biggerNodeIndex])
      {
        //交换 k 节点和较大子节点的值
        swap(data, k, biggerNodeIndex);
        //将 biggerNodeIndex 赋给 k，开始下一次 while 循环
        //保证 k 节点的值始终大于左右子节点的值
        k = biggerNodeIndex;
      } else
      {
        break;
      }
    }
  }
}

//交换 data 数组中 i,j 两个索引处的元素
private static void swap(int[] data, int i, int j)
{
  int temp = data[i];
  data[i] = data[j];
  data[j] = temp;
}

冒泡排序

原理：气泡在水底时，水压最大，气泡最小；但慢慢浮上水面时，气泡由小逐渐变大。当有 n 个元素时算法执行 n-1 次扫描，第 i 次扫描执行 n-i 次比较。

public static void bubbleSort(int[] origin)
{
  for (int i = 1; i < origin.length; i++)
  {
    int flag = 0;//flag标记用来记录是否有执行过交换动作，并记录次数
    for (int j = 0; j < origin.length - i; j++)
    {
      if (origin[j] > origin[j + 1])
      {
        int temp = origin[j];
        origin[j] = origin[j + 1];
        origin[j + 1] = temp;
        flag++;
      }
    }
    if (flag == 0)
    {
      break;
    }
  }
}

快速排序

快速排序法又称为分割交换排序法，是速度非常快的交换排序法。

假设有 n 个记录，快速排序法的步骤如下：

取 K 为第一个键值。
定义一个变量 i，i 变量从左边第一个索引开始，找大于分界值的元素的索引，并用 i 来记录该索引。
定义一个变量 j，j 变量从右边第一个索引开始，找小于分界值的元素的索引，并用 j 来记录该索引。
如果 i < j，交换 i、j 两个索引处的元素。
重复执行 1、2、3 步骤，直到 i >= j，则将 K 与 j 索引处的数据元素交换，并以 j 为基准点将数据分为左右两部分，并以递归方式分别为左右两半进行排序，直至完成排序。

/**
 * 快速排序
 *
 * @param origin 原始数组
 */
public static void quickSort(int[] origin)
{
  subSort(origin, 0, origin.length - 1);
}
  
private static void subSort(int[] data, int start, int end)
{
  if (start < end)
  {
    //把第一个数据元素作为分界值
    int base = data[start];
    //i 从左边开始搜索第一个比分界值大的数据元素的索引
    int i = start;
    //j 从右边开始搜索第一个比分界值小的数据元素的索引
    int j = end + 1;
    while (true)
    {
      //开始寻找大于分界值的索引，
      while (i < end && data[++i] < base) ;
      //寻找小于分界值的索引
      while (j > start && data[--j] > base) ;
      if (i < j)
      {
        swap(data, i, j);
      } else
      {
        break;
      }
    }
    swap(data, start, j);
    //分别递归左子列和右子列
    subSort(data, start, j - 1);
    subSort(data, j + 1, end);
  }
}

快速排序的时间效率很好，因为它每趟能确定的元素呈指数增长。

快速排序需要使用递归，而递归使用栈，因此它的空间效率为 O(log~2~n)。

快速排序中包含跳跃式交换，因此是不稳定算法。

直接插入排序

直接插入排序是将数组中的元素，逐一与已排序好的数据作比较，再将该元素插入适当的位置。

在步骤二中，以 4 为基准与其他元素比较后，放到适当位置(6的前面)，步骤三则拿 9 与其他两个元素比较，接着 8 在比较完前三个数后插入 9 的前面….直至完成排序。

public static void insertSort(int[] origin)
{
  //扫描次数为 n-1 次
  for (int i = 1; i < origin.length; i++)
  {
    int temp = origin[i];
    if (origin[i] < origin[i - 1])
    {
      int j = i - 1;
      for (; j >= 0 && origin[j] > temp; j--)
      {
        origin[j + 1] = origin[j];
      }
      origin[j + 1] = temp;
    }
  }
}

折半插入排序

折半插入排序是对直接插入排序的简单改进，它利用了每一趟比较时前面 0~i-1 个元素已经有序这个特点，不断对进行二分查找，确定第 i 个元素的插入位置。

public static void binaryInsertSort(int[] origin)
  {
    for (int i = 1; i < origin.length; i++)
    {
      int temp = origin[i];
      int begin = 0;
      int end = i - 1;
      while (begin <= end)
      {
        //找出 begin、end 中间的索引
        int mid = (begin + end) / 2;
        //如果 temp 值大于 begin、end 的中间元素的值
        if (temp > origin[mid])
        {
          //限制在索引大于 mid 的那一半进行搜索
          begin = mid + 1;
        } else
        {
          //限制在索引小于 mid 的那一半进行搜索
          end = mid - 1;
        }
      }
      //定位完成后把 begin 到索引 i 处的所有元素向后整体移一位
      for (int j = i; j > begin; j--)
      {
        origin[j] = origin[j - 1];
      }
      //把 temp 值插入
      origin[begin] = temp;
    }
  }

Shell排序

希尔排序法类似于直接插入排序法，但它可以减少数据搬移的次数。排序的原则是将数据区划分成特定间隔的几个小区块，以插入排序法排序完区块内的数据后再渐渐减少间隔的距离。

public static void shellSort(int[] origin)
{
  int h = 1;
  while (h <= origin.length / 3)
  {
    h = h * 3 + 1;
  }
  while (h > 0)
  {
    for (int i = h; i < origin.length; i++)
    {
      int temp = origin[i];
      if (origin[i] < origin[i - h])
      {
        int j = i - h;
        for (; j >= 0 && origin[j] > temp; j -= h)
        {
          origin[j + h] = origin[j];
        }
        origin[j + h] = temp;
      }
    }
    h = (h - 1) / 3;
  }
}

归并排序

归并排序的基本思想是将两个(或以上)有序的序列合并成一个新的有序序列。具体做法是，归并排序先将长度为 n 的无序序列看成是 n 个长度为 1 的有序子列，首先做两两合并，得到 n/2 个长度为 2 的有序子列，再做两两合并······不断重复这个过程，最终可以得到一个长度为 n 的有序序列。

对于长度为 n 的原始数据序列，只需经过 log~2~n 次合并。

归并排序的具体步骤：

定义变量 i，j 从 0 开始，依次等于 A 序列中每个元素的索引。
定义变量 i，j 从 0 开始，依次等于 B 序列中每个元素的索引。
拿 A 序列中 i 索引处元素和 B 序列中 j 索引处的元素进行比较，将较小的复制到一个临时数组中。
如果 i 索引处的元素小，i++；如果 j 索引处的元素小，j++。
不断重复以上 4 个步骤，即可将 A、B 两个序列中的数据元素复制到临时数组中，直到其中一个数组中的所有元素都被复制到临时数组中。最后，再将另一个数组中多出来的元素全部复制到临时数组中，合并即完成排序。

桶式排序

桶式排序不是一种基于比较的排序方法，其需要原始数据序列满足如下两个特征：

原始数据序列的所有值处于一个可枚举范围内；
原始数据序列所在的这个可枚举范围不应该太大，否则排序开销太大。

以数据 5、4、2、4、1 为例进行示范，这个待排序的序列处于 0 到 5 这个可枚举范围内，而且这个范围很小。具体步骤如下：

对这个可枚举范围构建一个 buckets 数组，用于记录落入每个桶中的元素的个数，于是可以得到如下的 buckets 数组：
对这个 buckets 数组的元素进行重新计算，按照公式：
$$
buckets[i]=buckets[i]+buckets[i-1];(其中 1<=i<buckets.length)
$$
，即可得到新的 buckets 数组：

桶式排序的巧妙在于，重新计算后的 buckets 数组元素保存了落入当前桶和落入前面所有桶中元素的总数目，而且定义的桶本身就是从小到大排列的。得出结论就是：每个 buckets 数组元素的值小于、等于落入当前桶中元素的个数。换句话说，落入当前桶中的元素在有序序列中应当排在 buckets 数组元素值所确定的位置。

桶式排序时间效率极高，它只要经过 2 轮遍历：第 1 轮遍历待排数据，统计每个待排数据落入各桶中的个数；第 2 轮遍历用于重新计算每个 buckets 数组元素的值。2 轮遍历后就可得到每个待排数据在有序序列中的位置，然后将各个数据项一次性放入指定位置即可。

桶式排序的空间开销较大，它需要两个数组：第 1 个 buckets 数组用于记录落入各桶中元素的个数，进而保存各元素在有序序列中的位置；第 2 个数组用于缓存待排数据。

public static void bucketSort(int[] origin, int min, int max)
  {
    int[] tempArray = new int[origin.length];
    int[] buckets = new int[max - min];
    //计算每个元素在序列出现的次数
    for (int i = 0; i < origin.length; i++)
    {
      buckets[origin[i] - min]++;
    }
    //计算 落入 各桶内的元素在有序序列中的位置
    for (int i = 1; i < max - min; i++)
    {
      buckets[i] = buckets[i] + buckets[i - 1];
    }
    //循环结束后，buckets 数组元素记录了 落入 前面所有桶
    //和 落入 当前 bucket 中元素的总数
    //就是说，buckets 数组元素的值代表了 落入 当前桶的元素在有序序列中的位置
    
    //将 origin 数组中数据完全复制到 tempArray 数组中缓存起来
    System.arraycopy(origin, 0, tempArray, 0, origin.length);
    //根据 buckets 数组中的信息将待排序的各元素放入相应的位置
    for (int k = origin.length - 1; k >= 0; k--)
    {
      origin[--buckets[tempArray[k] - min]] = tempArray[k];
    }
  }

基数排序

基数排序法并不需要进行元素间的比较，属于一种分配模式排序方式。按照比较的方向可分为 最高位优先(Most Significant Digit First,MSD)，和 最低位优先(Least Significant Digit First,LSD) 两种。MSD 法是从最左边的位数开始比较，而 LSD 是从最右边的位数开始比较。

下面以 LSD 为例对三位数的整数按个位数、十位数、百位数进行排序。

最后合并即完成排序：7、34、45、59、60、88、95、133、168、171、259、372.

基数排序法分析：

在所有情况下，时间复杂度均为 O(nlog~p~k)，k 是原始数据的最大值。
基数排序法是稳定排序。
基数排序会用到很大的额外空间来存放列表数据，其空间复杂度为 O(n*p)，n 是原始数据的个数，p 是数据字符数(即数据的位数)。
若 n 很大，p 固定或很小，基数排序将很有效率。

/**
 * 基数排序
 *
 * @param origin 原始数组
 * @param radix  指定关键字拆分的进制，如 radix=10，表明按 10 进制拆分
 * @param d      指定将关键字拆分成几个子关键字
 */
public static void radixSort(int[] origin, int radix, int d)
{
  int[] tempArray = new int[origin.length];
  //buckets 数组是桶式排序必须 buckets 数组
  int[] buckets = new int[radix];
  //依次从最高位的子关键字对待排序数据进行排序
  //下面循环中 rate 用于保存当前计算的位
  for (int i = 0, rate = 1; i < d; i++)
  {
    //重置 count 数组，开始统计第 2 个关键字
    Arrays.fill(buckets, 0);
    //将 origin 数组的元素复制到缓存数组中进行缓存
    System.arraycopy(origin, 0, tempArray, 0, origin.length);
    //计算每个待排序数据的子关键字
    for (int j = 0; j < origin.length; j++)
    {
      //计算数据指定位上的子关键字
      int subKey = (tempArray[j] / rate) % radix;
      buckets[subKey]++;
    }
    for (int j = 1; j < radix; j++)
    {
      buckets[j] = buckets[j] + buckets[j - 1];
    }
    //按子关键字对指定数据进行排序
    for (int m = origin.length - 1; m >= 0; m--)
    {
      int subKey = (tempArray[m] / rate) % radix;
      origin[--buckets[subKey]] = tempArray[m];
    }
    rate *= radix;
  }
}