排序算法

参考C++算法，这里面有些写法也值得商榷。

1. 冒泡排序算法

冒泡排序算法代码和思路比较简单，大家如果在面试时被要求实现排序时，可以用这种方法来实现。

该算法里，会统一地遍历待排序的数据，每次比较两个相邻的数据，如果它们顺序错误，比如要求是降序，但它们是升序，就交换这两个数据。

实现逻辑

• 比较相邻的元素。如果第一个比第二个大，就交换他们两个。
• 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。
• 针对所有的元素重复以上的步骤，除了最后一个。
• 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。
  通过两层循环控制：
• 第一个循环（外循环），负责把需要冒泡的那个数字排除在外；
• 第二个循环（内循环），负责两两比较交换。

性能分析

• 平均时间复杂度：O(N^2)
• 最佳时间复杂度：O(N)
• 最差时间复杂度：O(N^2)
• 空间复杂度：O(1)
• 排序方式：In-place

算法实现

// 冒泡排序改进(C++)
void bubble_sort(int arr[], int len)
{
    for (int i = len-1; i > 0; i--)
   {         
        bool  bExchange  = false;
        for (int j = 0; j < i; j++)
        {    
            if (arr[j] > arr[j + 1])
            {     
               bExchange = true;   
                swap(arr[j], arr[j + 1]);            
            }
        } 
        if(!Exchange)
        { 
             break;
        }
    }
}

稳定性

在相邻数据一样时不会交换位置，所以冒泡排序是稳定的。

2. 选择排序

选择排序(Selection sort)是一种简单直观的排序算法。

基本思想

• 首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，
• 然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。
• 以此类推，直到所有元素均排序完毕。

选择排序的思想其实和冒泡排序有点类似，都是在一次排序后把最小的元素放到最前面，或者将最大值放在最后面。但是过程不同，冒泡排序是通过相邻的比较和交换。而选择排序是通过对整体的选择，每一趟从前往后查找出无序区最小值，将最小值交换至无序区最前面的位置。

实现逻辑

① 第一轮从下标为 1 到下标为 n-1 的元素中选取最小值，若小于第一个数，则交换
② 第二轮从下标为 2 到下标为 n-1 的元素中选取最小值，若小于第二个数，则交换
③ 依次类推下去……

复杂度分析

• 平均时间复杂度：O(N^2)
• 最佳时间复杂度：O(N^2)
• 最差时间复杂度：O(N^2)
• 空间复杂度：O(1)
• 排序方式：In-place
• 稳定性：不稳定

该算法的实现步骤

template<typename T>
void SlectionSort(T arr[], int len)
{
    int i,  j,  min,  temp;
    for(i = 0; i < len -1; i++)
    {
        int min = i;
        for(j = i + 1; j < len; j++)
        {
            if(arr[j] < arr[min])
            {
                min = j;
            }
        }
        temp = arr[min];
        arr[min] = arr[i];
        arr[i] = temp;
    }
}

稳定性

基于数组实现的选择排序是不稳定的，但基于链表实现的是稳定的。
不过排序算法一般是基于数组的，所以排序算法一般是不稳定的。

3. 插入排序（Insertion Sort）

插入排序（Insertion-Sort）的算法描述是一种简单直观的排序算法。打过扑克牌的应该都会明白（当然，如果你说你打扑克牌摸牌的时候从来不按牌的大小整理牌，那我只能呵呵了）

基本思想

插入排序的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。插入排序在实现上，通常采用in-place排序（即只需用到O(1)的额外空间的排序），因而在从后向前扫描过程中，需要反复把已排序元素逐步向后挪位，为最新元素提供插入空间。

实现逻辑

① 从第一个元素开始，该元素可以认为已经被排序
② 取出下一个元素，在已经排序的元素序列中从后向前扫描
③如果该元素（已排序）大于新元素，将该元素移到下一位置
④ 重复步骤③，直到找到已排序的元素小于或者等于新元素的位置
⑤将新元素插入到该位置后
⑥ 重复步骤②~⑤

算法实现

void InsertionSort(int[] arr, int len)
{
    for (int i = 1;  i < len;  i++)
   {
        int val = arr[i];
        int pos = i;
        while (pos > 0 && arr[pos-1] > val)
        {
            arr[pos] = arr[pos-1];
            pos--;
        }
        arr[pos] = val;
    }
}

稳定性

由于只需要找到不大于当前数据的位置，所以相同的数据不需交换，所以插入排序是稳定。

4. 归并排序

归并排序，是创建在归并操作上的一种有效的排序算法。算法是采用分治法（Divide and Conquer）的一个非常典型的应用，且各层分治递归可以同时进行。归并排序思路简单，速度仅次于快速排序，为稳定排序算法，一般用于对总体无序，但是各子项相对有序的数列。

基本思想

归并排序是用分治思想，分治模式在每一层递归上有三个步骤：

• 分解（Divide）：将n个元素分成个含n/2个元素的子序列。
• 解决（Conquer）：用合并排序法对两个子序列递归的排序。
• 合并（Combine）：合并两个已排序的子序列已得到排序结果。

复杂度分析

• 平均时间复杂度：O(nlogn)
• 最佳时间复杂度：O(n)
• 最差时间复杂度：O(nlogn)
• 空间复杂度：O(n)
• 排序方式：In-place
• 稳定性：稳定

实现逻辑

迭代法

① 申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列
② 设定两个指针，最初位置分别为两个已经排序序列的起始位置
③ 比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置
④ 重复步骤③直到某一指针到达序列尾
⑤ 将另一序列剩下的所有元素直接复制到合并序列尾

递归法

① 将序列每相邻两个数字进行归并操作，形成floor(n/2)个序列，排序后每个序列包含两个元素
② 将上述序列再次归并，形成floor(n/4)个序列，每个序列包含四个元素
③ 重复步骤②，直到所有元素排序完毕

算法实现

迭代法

/ 归并排序（C++-迭代版）
template<typename T>
void merge_sort(T arr[], int len) {
    T* a = arr;
    T* b = new T[len];
    for (int seg = 1; seg < len; seg += seg) {
        for (int start = 0; start < len; start += seg + seg) {
            int low = start, mid = min(start + seg, len), high = min(start + seg + seg, len);
            int k = low;
            int start1 = low, end1 = mid;
            int start2 = mid, end2 = high;
            while (start1 < end1 && start2 < end2)
                b[k++] = a[start1] < a[start2] ? a[start1++] : a[start2++];
            while (start1 < end1)
                b[k++] = a[start1++];
            while (start2 < end2)
                b[k++] = a[start2++];
        }
        T* temp = a;
        a = b;
        b = temp;
    }

    if (a != arr) {
        for (int i = 0; i < len; i++)
            b[i] = a[i];
        b = a;
    }

    delete[] b;
}

递归法

tamplate<typename T>
void MergeSortRecursive(T arr[], T reg[], int start, int end)
{
    if(start >= end)
        return;
    int len = end - start;
    int mid = (len >>1) + start;
    int start1 = start, end1 = mid;
    int start2 = mid + 1, end2 = end;
    MergeSortRecursive(arr, reg, start1, end1);
    MergeSortRecursive(arr, reg, start2, end2);
    
    int k = start;
    while(start1 <= end1 && start2 <= end2)
        reg[k++] = arr[start1]  < arr[start2] ? arr[start1++] : arr[start2++]
    while(start1 <= end1)
        reg[k++] = arr[start1++];
    while(start2 < end2)
        reg[k++] = arr[start2++];
    for(k = start; k < end, k++)
        arr[k] = reg[k];
}

template<typename T>
void MergSort(T arr[], const int len)
{
    T reg[len];
    MergeSortRecursive(arr, reg, 0, len -1);
}

稳定性

因为遇到相等的数据时，是按顺序放在辅助的子序列里，所以，归并排序是稳定的。

5. 快速排序

快速排序在大数据情况下性能比较优秀，而且实现比较简单，所以也有比较广泛的应用。

算法描述

1. 从序列中找个元素，称为"基准"（pivot），
2. 重新排序数列，把比基准值小的数放在基准前，把比基准值大的元素放在后面，相同的数可放到任何一边。这样在本次操作结束之后，该基准就处于数列的中间位置。这个称为分区（partition）操作。
3. 再递归操作把小于基准值元素的子数列和大于基准值元素的子数列，用上述第1和第2步的方法进行排序。

算法实现

void quickSort(int a[], int low ,int high)
{
    if(low<high)  //判断是否满足排序条件，递归的终止条件
    {
        int i = low, j = high;   //把待排序数组元素的第一个和最后一个下标分别赋值给i,j，使用i,j进行排序；
        int x = a[low];    //将待排序数组的第一个元素作为哨兵，将数组划分为大于哨兵以及小于哨兵的两部分                                   
        while(i<j)  
        {
          while(i<j && a[j] >= x) j--;  //从最右侧元素开始，如果比哨兵大，那么它的位置就正确，然后判断前一个元素，直到不满足条件
          if(i<j) a[i++] = a[j];   //把不满足位次条件的那个元素值赋值给第一个元素，（也即是哨兵元素，此时哨兵已经保存在x中，不会丢失）并把i的加1
          while(i<j && a[i] <= x) i++; //换成左侧下标为i的元素开始与哨兵比较大小，比其小，那么它所处的位置就正确，然后判断后一个，直到不满足条件
          if(i<j) a[j--] = a[i];  //把不满足位次条件的那个元素值赋值给下标为j的元素，（下标为j的元素已经保存到前面，不会丢失）并把j的加1
        } 
            a[i] = x;   //完成一次排序，把哨兵赋值到下标为i的位置，即前面的都比它小，后面的都比它大
        quickSort(a, low ,i-1);  //递归进行哨兵前后两部分元素排序 ， low,high的值不发生变化，i处于中间
        quickSort(a, i+1 ,high);
    }
}

稳定性

由于在算法实现过程中无法保证相等的数据按顺序被扫描和按顺序存放，所以该算法不是稳定的。

6. 堆排序

堆排序

7. 希尔排序

在希尔排序算法出现前，计算机界普遍存在“排序算法不可能突破O(n平方)”的观点。希尔排序是第一个突破O(n平方)的排序算法，它是简单插入排序的改进版。希尔排序主要基于以下两点：

1. 插入排序算法在数组基本有序的情况下，可以近似地达到O(n)复杂度，有较高的效率。
2. 但是插入排序每次只能将数据移动一位，在数组较大且基本无序的情况下，性能会迅速恶化。

算法描述

先将整个待排序的记录序列拆分成为若干子序列，再分别进行直接插入排序，具体算法描述：

• 选择一个增量序列t1，t2，…，tk，其中ti>tj，tk=1；
• 按增量序列的个数k，对序列进行 k 趟排序；
• 每次排序，根据对应的增量ti，将待排序列拆分成若干长度为m 的子序列，分别对各个子表进行插入排序。

算法实现

public static void shellSort(int[] arr){
    int delta = 1;
    while (delta < arr.length/3){//generate delta
        delta=delta*3+1;    // <O(n^(3/2)) by Knuth,1973>: 1, 4, 13, 40, 121, ...
    }         
    int temp;
    for (; delta>=1; delta/=3){
        for (int i=delta; i<arr.length; i++){              
            for (int j=i; j>=delta && arr[j]<arr[j-delta]; j-=delta){
                temp = arr[j-delta];
                arr[j-delta] = arr[j];
                arr[j] = temp;
            }
        }//loop i
    }//loop delta
}

希尔排序的增量讨论

希尔排序的增量数列可以任取，需要的唯一条件是最后一个一定为1（因为要保证按1有序）。但是，不同的数列选取会对算法的性能造成极大的影响。
下面是一些常见的增量序列。
第一种增量是最初Donald Shell提出的增量，即折半降低直到1。据研究，使用希尔增量，其时间复杂度还是O(n平方)。

第二种增量Hibbard：{1, 3, ..., 2k-1}。该增量序列的时间复杂度大约是O(n的1.5次方)。

第三种增量Sedgewick增量：(1, 5, 19, 41, 109,...)，其生成序列或者是94i - 92i + 1或者是4i - 3*2i + 1。

稳定性

插入排序是稳定算法。但是，Shell排序是一个多次插入的过程。在一次插入中能确保不移动相同元素的顺序，但在多次的插入中，相同元素完全有可能在不同的插入轮次被移动，最后稳定性被破坏，因此，该排序排序不是一个稳定的算法。

8 计数排序

计数排序不是基于比较的排序算法，它的核心做法是，把输入的数据值转化为键存储在新开辟的数组里。 作为一种线性时间复杂度的排序，计数排序要求输入的数据必须是有确定范围的整数。

算法描述

1. 找出待排序的数组中最大和最小的元素；
2. 统计数组中每个值为i的元素出现的次数，存入数组C的第i项；
3. 对所有的计数累加（从C中的第一个元素开始，每一项和前一项相加）；
4. 反向填充目标数组：将每个元素i放在新数组的第C(i)项，每放一个元素就将C(i)减去1。

算法实现

public static void countSort(int[] a, int max, int min) {
     int[] b = new int[a.length];//存储数组
     int[] count = new int[max - min + 1];//计数数组

     for (int num = min; num <= max; num++) {
        //初始化各元素值为0，数组下标从0开始因此减min
        count[num - min] = 0;
     }

     for (int i = 0; i < a.length; i++) {
        int num = a[i];
        count[num - min]++;//每出现一个值，计数数组对应元素的值+1
     }

     for (int num = min + 1; num <= max; num++) {
        //加总数组元素的值为计数数组对应元素及左边所有元素的值的总和
        count[num - min] += sum[num - min - 1]
     }

     for (int i = 0; i < a.length; i++) {
          int num = a[i];//源数组第i位的值
          int index = count[num - min] - 1;//加总数组中对应元素的下标
          b[index] = num;//将该值存入存储数组对应下标中
          count[num - min]--;//加总数组中，该值的总和减少1。
     }

     //将存储数组的值一一替换给源数组
     for(int i=0;i<a.length;i++){
         a[i] = b[i];
     }
}

稳定性

该排序算法是稳定的。

9 桶排序

桶排序是计数排序的升级版，其工作原理是将数组分到有限数量的桶子里，然后对每个桶子再分别排序（有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排序），最后将各个桶中的数据有序的合并起来。

算法描述

1. 找出待排序数组中的最大值max、最小值min
2. 用动态数组ArrayList 作为桶，桶里放的元素也用 ArrayList 存储。桶的数量为(max-min)/arr.length+1
3. 遍历数组 arr，计算每个元素 arr[i] 放的桶
4. 每个桶各自进行排序
5. 再遍历桶数组，把排序好的元素放进输出数组

如下能看到大致的过程。

桶排序

算法实现

public static void bucketSort(int[] arr){
    int max = Integer.MIN_VALUE;
    int min = Integer.MAX_VALUE;
    for(int i = 0; i < arr.length; i++){
        max = Math.max(max, arr[i]);
        min = Math.min(min, arr[i]);
    }
    //桶数
    int bucketNum = (max - min) / arr.length + 1;
    ArrayList<ArrayList<Integer>> bucketArr = new ArrayList<>(bucketNum);
    for(int i = 0; i < bucketNum; i++){
        bucketArr.add(new ArrayList<Integer>());
    }
    //将每个元素放入桶
    for(int i = 0; i < arr.length; i++){
        int num = (arr[i] - min) / (arr.length);
        bucketArr.get(num).add(arr[i]);
    }
    //对每个桶进行排序
    for(int i = 0; i < bucketArr.size(); i++){
        Collections.sort(bucketArr.get(i));
    }
    System.out.println(bucketArr.toString());
}

稳定性

可以看到在分桶和从桶依次输出的过程是稳定的。但是由于在对每个桶进行排序时使用了其他算法，所以，桶排序的稳定性依赖于这些算法的稳定性，比如在对每个桶进行排序时用到了快速排序法等不稳定的算法时，整个桶排序算法就不是不稳定的。

10 基数排序

基数排序(Radix Sort)是桶排序的扩展，其基本思想是：把整数按位数切割成不同的数字，然后按每个位数分别比较。
排序过程是，把所有待比较数值（正整数）统一为同样的数位长度，数位较短的数前面的位数补零，随后从最低位开始，依次进行一次排序。这样从最低位一直到最高位排序完成后,该数列就成了一个有序的序列。

算法描述

1. 取得数组中的最大数，并取得位数；
2. arr为原始数组，从最低位开始取每个位组成radix数组；
3. 对radix进行计数排序（利用计数排序适用于小范围数的特点）；

算法实现

public abstract class Sorter {
     public abstract void sort(int[] array);
}

public class RadixSorter extends Sorter {

     private int radix;

     public RadixSorter() {
          radix = 10;
     }

     @Override
     public void sort(int[] array) {
          // 数组的第一维表示可能的余数0-radix，第二维表示array中的等于该余数的元素
          // 如：十进制123的个位为3，则bucket[3][] = {123}
          int[][] bucket = new int[radix][array.length];
          int distance = getDistance(array); // 表示最大的数有多少位
          int temp = 1;
          int round = 1; // 控制键值排序依据在哪一位
          while (round <= distance) {
               // 用来计数：数组counter[i]用来表示该位是i的数的个数
               int[] counter = new int[radix];
               // 将array中元素分布填充到bucket中，并进行计数
               for (int i = 0; i < array.length; i++) {
                    int which = (array[i] / temp) % radix;
                    bucket[which][counter[which]] = array[i];
                    counter[which]++;
               }
               int index = 0;
               // 根据bucket中收集到的array中的元素，根据统计计数，在array中重新排列
               for (int i = 0; i < radix; i++) {
                    if (counter[i] != 0)
                         for (int j = 0; j < counter[i]; j++) {
                              array[index] = bucket[i][j];
                              index++;
                         }
                    counter[i] = 0;
               }
               temp *= radix;
               round++;
          }
     }

     private int getDistance(int[] array) {
          int max = computeMax(array);
          int digits = 0;
          int temp = max / radix;
          while(temp != 0) {
               digits++;
               temp = temp / radix;
          }
          return digits + 1;
     }

     private int computeMax(int[] array) {
          int max = array[0];
          for(int i=1; i<array.length; i++) {
               if(array[i]>max) {
                    max = array[i];
               }
          }
          return max;
     }
}

稳定性

通过上面的排序过程可以看到，每一轮操作，都按从左到右的顺序进行，如果出现相同的元素，则会保持它们在原始数组中的顺序。所以基数排序是一种稳定的排序。

最后再整理下各算法的时间和空间复杂度，以及它们的稳定性。

image.png