0

本文记录了各种排序算法，相应性质；面试中的考察。
原文地址：https://hit-alibaba.github.io/interview/basic/algo/Sorting.html

算法小白——基本排序算法入门（动图演示）

常见的稳定排序算法有：

冒泡排序（Bubble Sort） — O(n²)
插入排序（Insertion Sort）— O(n²)
桶排序（Bucket Sort）— O(n); 需要 O(k) 额外空间
计数排序 (Counting Sort) — O(n+k); 需要 O(n+k) 额外空间
合并排序（Merge Sort）— O(nlogn); 需要 O(n) 额外空间
二叉排序树排序 （Binary tree sort） — O(n log n) 期望时间; O(n²)最坏时间; 需要 O(n) 额外空间
基数排序（Radix sort）— O(n·k); 需要 O(n) 额外空间

常见的不稳定排序算法有：

选择排序（Selection Sort）— O(n²)
希尔排序（Shell Sort）— O(nlogn)
堆排序（Heapsort）— O(nlogn)
快速排序（Quicksort）— O(nlogn) 期望时间, O(n²) 最坏情况; 对于大的、乱数串行一般相信是最快的已知排序

冒泡排序

冒泡排序是最简单最容易理解的排序算法之一；
其思想是通过无序区中相邻记录关键字间的比较和位置的交换；
在最好情况下，即正序有序，则只需要比较n次。故，为O(n) ，最坏情况下，即逆序有序，则需要比较(n-1)+(n-2)+……+1，故，为O(n²)。
最大的元素移动最快，最小的元素移动最慢。

在冒泡排序中：

1. 最大元素 - 的移动速度是最快的，哪怕一开始最大元素处于序列开头，也可以在一轮内层循环之后，移动到序列末尾；（向后比较，且持续向后移动）
2. 最小元素 - 每一轮内层循环只能向前挪动一位。如果最小元素在序列末尾，就需要 n-1 次交换才能移动到序列开头。（向后比较；前移后，指针不再指向该元素。）

最大元素可以一轮循环中移动到数列最末尾。（没次比较，更大，往后移动一位）
最小

（最坏case：）

优化算法2.0

进一步地，在每轮循环之后，可以确认，最后一次发生交换的位置之后的元素，都是已经排好序的，因此可以不再比较那个位置之后的元素，大幅度减少了比较的次数：

private static void BubbleSort(int[] array)
{
    var n = array.Length;
    for (var i = 0; i < array.Length - 1; i++)
    {
        var newn = 0;
        for (var j = 0; j < n - 1; j++)
        {
            if (array[j] > array[j + 1])
            {
                Swap(array, j, j+1);
                newn = j + 1;   // newn 以及之后的元素，都是排好序的
            }
        }

        n = newn;

        if (n == 0)
        {
            break;
        }
    }
}

（newn - 指向的是 最后一个换过位置的 元素）
（而且这个换过位置 的元素，比后面的元素都小（所以才没有交换））
（它之后的元素都没有换过位置，是从小到大的）

优化算法 3.0

更进一步地，为了优化之前提到的乌龟和兔子问题，可以进行双向的循环，正向循环把最大元素移动到末尾，逆向循环把最小元素移动到最前，这种优化过的冒泡排序，被称为鸡尾酒排序：

private static void CocktailSort(int[] array)
{
   var begin = 0;
   var end = array.Length - 1;
   while (begin <= end)
   {
   var newBegin = end;
   var newEnd = begin;

   for (var j = begin; j < end; j++)
   {
       if (array[j] > array[j + 1])
       {
       Swap(array, j, j + 1);
       newEnd = j + 1;
       }
   }

   end = newEnd - 1;

   for (var j = end; j > begin - 1; j--)
   {
       if (array[j] > array[j + 1])
       {
       Swap(array, j, j + 1);
       newBegin = j;
       }
   }

   begin = newBegin + 1;
   }
}

关于鸡尾酒排序的具体请见：
http://bubkoo.com/2014/01/15/sort-algorithm/shaker-sort/

？？Running time？？？

插入排序

一般来说，插入排序都采用in-place在数组上实现。具体算法描述如下：

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

插入排序

插入排序也是一个简单的排序算法，它的思想是，每次只处理一个元素，从后往前查找，找到该元素合适的插入位置，最好的情况下，即正序有序(从小到大)，这样只需要比较n次，不需要移动。因此时间复杂度为O(n) ，最坏的情况下，即逆序有序，这样每一个元素就需要比较n次，共有n个元素，因此实际复杂度为O(n²) 。

private static void InsertionSort(int[] array)
{
    int i = 1;
    while (i < array.Length)
    {
    var j = i;
    while (j > 0 && array[j - 1] > array[j])
    {
        Swap(array, j, j - 1);
        j--;
    }

    i++;
    }
}

QuickSort

摘自：常见排序算法 - 快速排序 (Quick Sort)/wikipedia

快速排序

分治法的基本思想是：将原问题分解为若干个规模更小但结构与原问题相似的子问题。递归地解这些子问题，然后将这些子问题的解组合为原问题的解。

利用分治法可将快速排序的分为三步：

1. 在数据集之中，选择一个元素作为”基准”（pivot）。
2. 所有小于”基准”的元素，都移到”基准”的左边；所有大于”基准”的元素，都移到”基准”的右边。这个操作称为分区 (partition) 操作，分区操作结束后，基准元素所处的位置就是最终排序后它的位置。
3. 对”基准”左边和右边的两个子集，不断重复第一步和第二步，直到所有子集只剩下一个元素为止。

分区算法

function partition(a, left, right, pivotIndex)
     pivotValue := a[pivotIndex]
     swap(a[pivotIndex], a[right])         // 把 pivot 移到結尾
     storeIndex := left                   // index一开始在最左边
     for i from left to right-1          // 把所有元素从左至右遍历一遍
         if a[i] < pivotValue
             swap(a[storeIndex], a[i])
             storeIndex := storeIndex + 1     // 从左边开始，填满所有比pivot小的元素
     swap(a[right], a[storeIndex])            // 把 pivot 移到它最後的地方
     return storeIndex // 返回 pivot 的最终位置（该位置左边=比pivot小的元素；
                       //右边=比pivot大的元素）

调用分区实现排序

一旦我们有了这个分区算法，要写快速排列本身就很容易：

procedure quicksort(a, left, right)
    if right > left
        select a pivot value a[pivotIndex]
        pivotNewIndex := partition(a, left, right, pivotIndex)
        quicksort(a, left, pivotNewIndex-1)
        quicksort(a, pivotNewIndex+1, right)

Quick Sort

注意第二行的两次交换：
* 即在i = 1,2 => 元素“7”“8”，并没有进行swap操作)
* 而是在i = 3,4 => 元素“4”“2”，4<5, 2<5，
  进行swap操作交换到storeIndex的位置（同时storeIndex++）