12种常用排序算法

本文仅作为个人学习排序算法的参考笔记，若想详细了解学习，请前往 http://blog.csdn.net/han_xiaoyang/article/details/12163251

tip：

• 文章中涉及的所有排序均为升序

• 文中会提及稳定算法和不稳定算法的概念，先贴一下百度的解释：假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中，ri=rj，且ri在rj之前，而在排序后的序列中，ri仍在rj之前，则称这种排序算法是稳定的；否则称为不稳定的。

插入排序算法

• 插入排序（Insertion Sort）的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。
• 空间代价O(1)
• 平均时间复杂度为O(n^2)，最好时间复杂度n-1，最坏时间复杂度n(n+1)/2
• 稳定的排序算法
• 插入排序不适合对于数据量比较大的排序应用。但是，如果需要排序的数据量很小，例如，量级小于千，那么插入排序还是一个不错的选择。

void insertionSort(int arr[]) 
{
    for(int i = 1; i < arr.length; i++)
    {
        int j = i - 1;
        int temp = arr[i];
        while((j >= 0) && (arr[j] > temp))
        {
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = temp;
    }
}

二分插入排序算法

• 二分（折半）插入（Binary insert sort)排序是一种在直接插入排序算法上进行小改动的排序算法。其与直接排序算法最大的区别在于查找插入位置时使用的是二分查找的方式，在速度上有一定提升。
• 稳定的排序算法
• 空间代价：O(1)
• 时间代价：插入每个记录需要O(log i)比较，最多移动i+1次，最少2次。最佳情况O(n log n)，最差和平均情况O(n^2)。
• 当n较大时，总排序码比较次数比直接插入排序的最差情况好得多，但比最好情况要差，所元素初始序列已经按排序码接近有序时，直接插入排序比二分插入排序比较次数少。二分插入排序元素移动次数与直接插入排序相同，依赖于元素初始序列。

void BinInsertSort(int arr[])
{
    for(int i = 1; i < arr.length; i++)
    {
        int left = 0;
        int right = i - 1;
        int temp = arr[i];
        while (left <= right) 
        {
            int middle = (left +right) / 2;
            if(arr[middle] > temp)
            {
                right = middle - 1;
            }
            else 
            {
                left = middle + 1;
            }
        }

        for(int j = i - 1; j >= left; j--)
        {
            arr[j + 1] = arr[j];
        }
        arr[left] = temp;
    }
}

小结：

• 插入排序：取一个元素，在已排序的元素中一一比较，满足条件就替换，直至不满足条件；
• 二分插入排序：取一个元素，在已排序的元素中，找到满足条件的位置i，让i + 1往后的元素后退一位，然后将取出的元素插入i位置

希尔排序

• 希尔排序的时间复杂度与增量序列的选取有关，例如希尔增量时间复杂度为O(n^{2)，而Hibbard增量的希尔排序的时间复杂度为O(N}(5/4))，但是现今仍然没有人能找出希尔排序的精确下界。
• 不稳定排序

void shellSort(int arr[]) 
{
    int gap = arr.length / 2; //在此增量取数组长度/2
    while(gap > 0)
    {
        for(int i = 0; i < gap; i++)
        {
            int j = i + gap;
            int temp = arr[j];
            while((temp < arr[i]) && (j < arr.length))
            {
                arr[j] = arr[i];
                j += gap;
            }
            arr[j] = temp;
        }
        gap /= 2;
    }
}

选择排序

• 选择排序(Selection sort)是一种简单直观的排序算法。工作原理如下：首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。
• 选择排序的交换操作介于0和(n-1)次之间
• 选择排序的比较操作为n(n-1)/2次之间，比较次数O(n^2)
• 选择排序的赋值操作介于0和3(n-1)次之间
• 交换次数O(n),最好情况是，已经有序，交换0次；最坏情况是，逆序，交换n-1次
• 交换次数比冒泡排序少，由于交换所需CPU时间比比较所需的CPU时间多，n值较小时，选择排序比冒泡排序快

复杂度	值
最差时间复杂度	О(n²)
最优时间复杂度	О(n²)
平均时间复杂度	О(n²)
最差空间复杂度	О(n) total, O(1)

void selectSort(int arr[]) 
{
    int length = arr.length;
    for(int i = 0; i < length; i++)
    {
        int min = arr[i];
        int index = i;
        int j = i + 1;
        while(j < length)
        {
            if(min > arr[j])
            {
                min = arr[j];
                index = j;
            }
            j++;
        }
        arr[index] = arr[i];
        arr[i] = min;
    }
}

快速排序

• 基本思想:通过一趟排序将待排记录分隔成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小，则可分别对这两部分记录继续进行排序
• 复杂度: 平均状况下，排序 n 个项目要Ο(n log n)次比较。在最坏状况下则需要Ο(n^2)次比较

复杂度	值
最差时间复杂度	О(n^2)
最优时间复杂度	O(n log n)
平均时间复杂度	O(n log n)
最差空间复杂度	根据实现的方式不同而不同

• 算法步骤:

1. 从数列中挑出一个元素，称为 "基准"（pivot）;
2. 排序数组，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面(相同的数可以到任一边)。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区(partition)操作。
3. 递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序。

function quickSort(first, end, array) {
        var key = array[first];//默认选择第一个为pivot
        var i = first;
        var j = end;
        if (first > end) {
            while (i < j) {
                /**
                 * 以 23 7 36 8 15 9 为例, 第一遍基准为23
                 */

                // 从数组最右边开始遍历, 如果比基准大, 则比较下一个; 如果比基准小, 则赋值到基准的位置
                while (array[j] > key && j > i) {
                    j--;
                }
                if (i < j) {
                    array[i++] = array[j];
                    // 赋值后, 数组排列为9 7 36 8 15 9  i=1 j=5
                    // 数组中有两个相同的数, 其中赋值到基准位置的数才是其正确位置, j位置上的则是可被替换的
                }

                // 从数组最左边开始遍历, 如果比基准小, 则比较下一个; 如果比基准大, 则赋值到j的位置
                while (array[i] < key && j > i) {
                    i++;
                }

                if (i < j) {
                    array[j--] = array[i];
                    // 赋值后, 数组排列为9 7 36 8 15 36  i=2 j=4
                    // 数组中有两个相同的数, 其中赋值到j位置的数才是其正确位置, i位置上的则是可被替换的
                }
                array[i] = key;
                // 将基准赋值到i位置 数组排序为9 7 23 8 15 36 
                // i=2 j=4 在进行一次以23为基准的循环
                // 得到 9 7 15 8 23 36  保证在23前的数都比23小, 在23后的数都比23大. 则以23为基准的排序结束, 跳出循环
            }

            quickSort(0, i - 1, array);
            quickSort(i + 1, array.length - 1, array);
        }
    }