排序算法代码 |

冒泡排序

冒泡排序算法的运作如下：

比较相邻的元素。如果第一个比第二个大，就交换他们两个。
对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。
针对所有的元素重复以上的步骤，除了最后一个。
持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

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

改进算法

冒泡排序是与插入排序拥有相等的运行时间，但是两种算法在需要的交换次数却很大地不同。
在最好的情况，冒泡排序需要O(n^2)次交换，而插入排序只要最多O(n)交换。
冒泡排序的实现通常会对已经排序好的数列拙劣地运行（O(n^2)），而插入排序在这个例子只需要O(n)个运算。
因此很多现代的算法教科书避免使用冒泡排序，而用插入排序替换之。
冒泡排序如果能在内部循环第一次运行时，使用一个旗标来表示有无需要交换的可能，也可以把最好的复杂度降低到O(n)。
在这个情况，已经排序好的数列就无交换的需要。若在每次走访数列时，把走访顺序反过来，也可以稍微地改进效率。
有时候称为鸡尾酒排序，因为算法会从数列的一端到另一端之间穿梭往返。

改进代码，使用一个旗标来表示有无需要交换的可能

void bubble_sort(int arr[], int len) {
    int i, j, temp;
    bool flag = true;
    for (i = 0; i < len - 1; i++) {
        flag = false;
        for (j = 0; j < len - 1 - i; j++) {
            if (arr[j] > arr[j + 1]) {
                temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
                flag = true;
            }
        }

        if(!flag)
            break;
    }
}

进一步优化，如果R[0..i]已是有序区间，上次的扫描区间是R[i..n]，
记上次扫描时最后一次执行交换的位置为lastSwapPos，则lastSwapPos在i与n之间，
不难发现R[i..lastSwapPos]区间也是有序的，否则这个区间也会发生交换；
所以下次扫描区间就可以由R[i..n] 缩减到[lastSwapPos..n]。

void bubble_sort(int arr[], int len) {
    int i, j, temp;
    int lastSwapPos = 0, lastSwapPosTemp = 0;
    for (i = 0; i < len - 1; i++) {
        lastSwapPos = lastSwapPosTemp;
        for (j = lastSwapPosTemp; j < len - 1 - i; j++) {
            if (arr[j] > arr[j + 1]) {
                temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
                lastSwapPosTemp = j;
            }
        }

        if(lastSwapPos == lastSwapPosTemp)
            break;
    }
}

鸡尾酒排序

鸡尾酒排序，也就是定向冒泡排序，是冒泡排序的一种变形。
此算法与冒泡排序的不同处在于排序时是以双向在序列中进行排序。
鸡尾酒排序等于是冒泡排序的轻微变形。不同的地方在于从低到高然后从高到低，而冒泡排序则仅从低到高去比较序列里的每个元素。

插入排序

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

快速排序

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

#归并排序

归并排序是建立在归并操作上的一种有效的排序算法。
该算法是采用分治法（Divide and Conquer）的一个非常典型的应用

步骤：

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

堆排序

堆积排序（Heapsort）是指利用堆这种数据结构所设计的一种排序算法。
堆是一个近似完全二叉树的结构，并同时满足堆性质：即子结点的键值或索引总是小于（或者大于）它的父节点。

选择排序

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

希尔排序

希尔排序，也称递减增量排序算法，是插入排序的一种高速而稳定的改进版本。
希尔排序是基于插入排序的以下两点性质而提出改进方法的：

插入排序在对几乎已经排好序的数据操作时，效率高，即可以达到线性排序的效率
但插入排序一般来说是低效的，因为插入排序每次只能将数据移动一位>

梳排序

梳排序是改良自冒泡排序和快速排序。

在冒泡排序算法中，只比较阵列中相邻的二项，即比较的二项的间距(Gap)是1，
梳排序提出此间距其实可大于1，改自插入排序的希尔排序同样提出相同观点。
梳排序中，开始时的间距设定为阵列长度，并在循环中以固定比率递减，通常递减率设定为1.24。
在一次循环中，梳排序如同冒泡排序一样把阵列从首到尾扫描一次，比较及交换两项，不同的是两项的间距不固定于1。
如果间距递减至1，梳排序假定输入阵列大致排序好，并以冒泡排序作最后检查及修正。