排序算法 | Trluper

1. 算法总览

常见的排序算法有插入排序、选择排序、希尔排序、堆排序、冒泡排序、快速排序、归并排序和基数排序。常见排序算法可以分为两大类：

非线性时间比较类排序：通过比较来决定元素间的相对次序，由于其时间复杂度不能突破O(nlogn)，因此称为非线性时间比较类排序。
线性时间非比较类排序：不通过比较来决定元素间的相对次序，它可以突破基于比较排序的时间下界，以线性时间运行，因此称为线性时间非比较类排序。排序算法的时间复杂度如下：

算法的稳定性：稳定性就是能保证排序前两个相等的数其在序列的前后位置顺序和排序后它们两个的前后位置顺序相同。

稳定排序算法：冒泡排序、插入排序、归并排序、计数排序、桶排序与基数排序
不稳定排序算法：希尔排序、选择排序、堆排序与快速排序

内部排序和外部排序：内部排序是数据记录在内存中进行排序，而外部排序是因排序的数据很大，一次不能容纳全部的排序记录，在排序过程中需要访问外存。上面所列举的都是内部排序。像多路归并可以采用外部排序

1.1 插入排序

基本思想：每次将当前元素插入到左侧（有序区）已经排序的数组中，使得插入之后的左侧数组依然有序。
- 查找出元素要插入的位置：要插的元素与之前排好的子序比较
- 将要插入位置的元素及后面的元素后移一个位置
- 将元素插入
复杂度：插入排序一共需要两重循环，第一重循环确定需要加入有序序列的新元素，一共n-1轮，第二重循环确定新元素在原来有序序列中的位置，平均需要n/4轮可以确定位O(n²),空间复杂度为O(1)
稳定性：每次比较时遇到第一个小于等于新元素的元素，就将新元素插入到该元素的后面，即可不破坏相等元素的相对顺序，做到算法稳定。

template<class T>
void insertSort(T& cap)
{
    int len = cap.size();
    if (len== 0)
        return;
    for (int i = 1; i < len; i++)
    {
        int tmp = cap[i];
        int j = i - 1;
        for (j; j >= 0 && cap[j] > tmp; j--)
            cap[j + 1] = cap[j];
        cap[j + 1] = tmp;
    }

}

1.2 希尔排序

通过上面对插入排序程序的编写知道，插入排序适用于基本有序和数据量不大的排序表，希尔排序是基于这两点改进而来的。

基本思想：先将待排序表分割成若干形如
1
L[i,i+d,i+2d……,i+kd]
既把步长相隔增量d的记录组成一个子表，对各个子表分别进行直接插入排序。当整个表的元素已呈“基本有序”时，再次对全体记录进行一次直接插入排序。一般来说，步长取d=n/2，之后都已1/2递减。
- 1.取一步长d1<n，把表中全部记录分发d组
- 2.所有距离为d1的倍数的记录放到一组。
- 3.在各组内进行直接插入排序
- 4.取第二个步长d2<d1，重复上述过程，直到d=1。
- 5.d=1时，再进行一次直接插入排序
复杂度：希尔排序的时间复杂度会随着d选取策略的不同而发生变化，但是通常保持在$O(n^{1.3})~O(n^{1.5})$;希尔排序依旧属于原地排序，不需要额外的空间，所以空间复杂度与插入排序一样为O(1)
稳定性：虽然插入排序是稳定的排序算法，但是希尔排序因为将序列进行了拆分再进行插入排序，如此不同组中的相等元素相对位置不能保证不变，所以相等元素的相对位置会发生改变，故时不稳定排序。

template<class T>
void shellSort(T& cap)
{
    int len = cap.size();
    if (len == 0)
        return;
    for (int d = len / 2; d >= 1; d /= 2)
    {
        for (int i = d; i <len ; i++) {
            int tmp = cap[i];
            int j;
            for (j = i - d; j >= 0 && cap[j] > tmp; j -= d)
                cap[j + d] = cap[j];
            cap[j + d] = tmp;
        }
    }
}

1.3 选择排序

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

基本思想：首先在未排序序列中找到最小（大）元素，存放到排序序列的起始（末尾）位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。
复杂度：选择排序一共需要比较n-1轮（每轮找到最小的元素进行交换），第m轮比较n-m次，所以比较的总次数为：$ _{i=0}^{n-1}n-i $，即为$O(N^2)$。选择排序不需要额外的空间，故其空间复杂度为$O(1)$
稳定性：由于选择出的元素可能会进行跨越式的交换，所以会破坏原本的顺序，所以不稳定。

//即使终止的选择排序
template<class T>
void selectionSort(T& cap)
{
    bool sorted = false;
    for (int size = cap.size(); !sorted && size > 1; size--)
    {		//每一轮size-1,最大的放在后面   
        int indexOfMax = 0;
        sorted = true;
        for (int i = 1; i < size; i++)
        {
            if (cap[indexOfMax] < cap[i])		//找出最大的值
                indexOfMax = i;
            else
                sorted = false;	//无序
        }
        Swap(cap[indexOfMax], cap[size - 1]);
    }
}

1.4 冒泡排序

基本思想：从后往前（从前往后），两两比较相邻元素的值。若为逆序A[i]<A[i-1]，则交换他们。每一轮将最大的放到后面（即每一次减少一次内循环）
复杂度：冒泡排序一共需要比较n-1轮，第m轮比较n-m次，所以其比较总次数应为：$\displaystyle\sum_{i=0}^{n-1}n-i$，故冒泡排序的时间复杂度为O(n²)。冒泡排序比较和交换的过程中不消耗额外的内存，故冒泡排序的空间复杂度为O(1)
稳定性：比较时如果两个元素相等则不交换，即可做到使算法稳定

//有序时及时终止的冒泡排序
template<class T>
void bubbleSort(T& cap) {
    bool sorted = true;
    for (int i = cap.size(); sorted && i > 1; i--) {
        sorted = false;
        for (int j = 0; j < i-1; j++)
            if (cap[j] > cap[j + 1]) {
                Swap(cap[j], cap[j + 1]);
                sorted = true;
            }
    }
}

1.5 快速排序**

基本思想：快速排序使用分治的思想，通过一趟排序将待排序列分割成两部分，其中一部分记录的关键字均比另一部分记录的关键字小。之后分别对这两部分记录继续进行排序，以达到整个序列有序的目的。
- 1.选择基准：在待排序列中，按照某种方式挑出一个元素，作为 “基准”（pivot）
- 2.分割操作：以该基准在序列中的实际位置，把序列分成两个子序列。此时，在基准左边的元素都比该基准小，在基准右边的元素都比基准大
- 3.递归地对两个序列进行快速排序，直到序列为空或者只有一个元素。
复杂度：快速排序的性能受到基准选择策略的影响，理论上如果每次选择基准都选择分区的第一个元素，那么这个序列越有序则时间复杂度越趋近于O(n²)，这是因为每次基准都是分区最大或最小的元素，那么左区间将会没有元素，而右区间将会有除了基准外的全部元素，这样就跟普通的插入排序没有区别了，因此对于快排会有优化措施。快速排序的最坏运行情况是O(n²)，比如说顺序数列的快排。但它的平摊期望时间是O(nlogn)，且O(nlogn) 记号中隐含的常数因子很小，比复杂度稳定等于 O(nlogn) 的归并排序要小很多。所以，对绝大多数顺序性较弱的随机数列而言，快速排序总是优于归并排序。快速排序可以实现原地排序，不需要消耗额外的内存，所以快速排序的空间复杂度为O(1)。
稳定性：快速排序不能保证相等元素的相对顺序不发生改变，所以不稳定。

//编写自己的quickSort,没有优化，遇到最坏情况的时间复杂度会变成O(N*N)
void quickSort(vector<int>& nums,int l,int r){
        if(r==l) return;
        int pivot=nums[l],left=l-1,right=r+1;
        while(left<right){
            do left++; while(nums[left]<pivot);
            do right--; while(nums[right]>pivot);
            if(left<right) swap(nums[left],nums[right]);
        }
        quickSort(nums,l,right);
        quickSort(nums,right+1,r);
}

1.5.1 快排优化

对于快排，其性能受到基准选择策略的影响，当出现下面两种情况时为最坏情况：

在分解时每次选取的基准点为最小元素
在分解时每次选取的基准点为最大元素

为了避免快排出现上述所说的最坏情况，选择哪一个元素作为基准点是关键，在快排过程中采用三点取中间值的优化方案。三数取中median-of-three指的是在挑选基准元素时，不是简单的选择数组中的第一个元素或最后一个，而是选取某三个元素，常选头、尾和中央三个元素，并且适用三个元素之中的中位数作为基准元素进行划分。这样即使在最坏的情况下将时间复杂度推进到O(NlogN)

//优化后的快排代码
void quickSort(vector<int>& nums,int l,int r){
        if(r==l) return;
		int pivot= medianOfThree(nums,l,r);
        int left=l-1,right=r+1;
        while(left<right){
            do left++; while(nums[left]<pivot);
            do right--; while(nums[right]>pivot);
            if(left<right) swap(nums[left],nums[right]);
        }
        quickSort(nums,l,right);
        quickSort(nums,right+1,r);
}

inline int medianOfThree(vector<int>& cap, int first, int last)
{
   int mid=(first+last)>>1;
   int l=cap[first],m=cap[mid],r=cap[last];
   int Min=min(min(l,m),r);
   int Max=max(max(l,m),r);
   return l^m^r^Min^Max;
}

上图对优化后和优化前的快排进行了测试，很明显三数取中后对与升序和降序数组的时间得到了大大的改善，避免了最坏情况，逼近O(NlogN),但是对于重复数组的优化还不能得到很好的改善，因此可以在三数取中的快排中加入以下的策略：

优化一：当待排序序列的长度分割到一定大小后，使用插入排序，这是因为对于很小部分大致有序的数组，快排不如插排效率。当待排序序列的长度分割到一定大小后，继续分割的效率比插入排序要差，此时可以使用插排而不是快排
优化二：当待排序序列的长度分割到一定大小后如100个，使用计数排序，这样能够很明显的提升大量重复值情况下的效率

1.6 堆排序*

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

大顶堆：每个节点的值都大于或等于其子节点的值，在堆排序算法中用于升序排列；

小顶堆：每个节点的值都小于或等于其子节点的值，在堆排序算法中用于降序排列；

基本思想：
- 插入：因为堆是完全二叉树，所以当加入一个元素形时，必须维持该堆仍为完全二叉树，即该新节点位置由此定下了肯定为叶子结点。接着元素插入要依据原来是大根堆还是小根堆（即不能破环该堆的性质）。把插入的元素，沿着从新节点到根节点的路径i/2，执行一趟冒泡操作，将新元素与其夫节点的元素比较交换，直到后者大于前者（大根堆为例）。
- 删除：在大根堆中删除一个元素，其实就是删除根节点的元素。此时就需要重新组织，以便保持性质不变。其策略是，从删除的位置开始为一个树,向下找，找到该树的最后一个叶子节点，删除该节点但保存元素到临时量；然后比较节点的左右孩子，将大的放到该根节点；这时因为大孩子的被放到根节点而成为了空(没有元素），以此类推，直到最后一个叶子我们与之前中间量保存的元素比较，完成删除排序，
- 初始化：当堆刚开始时就要有n个元素，我们就要构建非空堆，我们需要在堆中执行n次插入操作。先将元素按层次插入，取位置在i=n/2的元素，如果以这个元素为根的子树是大根堆则不做操作，如果不是大根堆则从该节点开始的树进行检测替换，依次检查i-1,i-2……1
复杂度：堆排序的时间复杂度是标准的O(nlogn)。用数组实现堆的功能，故空间复杂度为O(1)
稳定性：堆排序并不是进行线性的比较，而是根据堆的结构进行比较，所以在交换时会破坏相等元素原本的相对顺序。

/*
堆插入
该方法通过查询当前堆的大小和元素比较定位插入点，进行大根堆完全二叉树形式插入即`/2`
*/
template<class T>
void push(T& heap,const T& theElement){
	int currentNode=++heapsize;
	//通过比较寻找插入点，比插入值小的元素下沉
	while(currentNode!=1&&heap[currentNode/2]<theElement)
	{
		heap[currentNode]=heap[currentNode/2];
		currentNode/=2;
	}
	//插入新值
	heap[currenNode]=theElement;
}

//堆删除
templaet<class T>
void pop(T& heap){
	if(heapsize==0)
		return;
	heap[1].~T();		//销毁根节点元素
	T lastElement=heap[heapsize];	//最后一个元素保存到临时变量
	heap[heapsize--].~T();			//销毁最后一个元素
	int currentNode=1,child=2;
	while(child<heapsize)
	{	//元素进行上升
		if(child<heapsize&&heap[child]<heap[child+1])
			child++;
		//判断lastElement是否可以放在heap[child]上
		if(lastElement>=heap[child])	//可以就直接退出
			break;
		heap[currentNode]=heap[child];
		currentNode=child;
		child*=2;
	}
	heap[currentNode]=lastElement;
}

template<class T>
void initial(T& Heap,std::size_t _heapsize){

	heapsize=_heapsize;
	//从下往上进行堆化，即从heapsize/2开始，直到root=1
	for(size_t root=heapsize/2;root>=1;root--)
	{
		T rootElement=heap[root];
		int child=2*root;
		while(child<=heapsize)
		{
			if(child<heapsize&&heap[child]<heap[child+1])
				child++;
			if(rootElement>=heap[child])
				break;
			heap[child/2]=heap[child];
			child*=2;
		}
	}
	heap[child/2]=rootElement
}

当然你也可以不用写堆排序，直接使用STL当中的push_heap、pop_heap、make_heap进行插入、删除和初始化一个堆。

1.7 基数排序*

基数排序是一种非比较型整数排序算法，其原理是将整数按位数切割成不同的数字，然后按每个位数分别比较。由于整数也可以表达字符串（比如名字或日期）和特定格式的浮点数，所以基数排序也不是只能使用于整数。

基本思想：基数排序排序主要通过将数字分解进行排序，如三位数的925，基数排序可通过十进制分解，将925分解成9、2、5三个数，然后依次以个位、十位、百位进行排序。在这个过程中，因为数字只有0~9,所有仅仅需要10个桶就，然后调用三次箱子排序即可：
- 1.将无序集合中的所有元素根据个位的大小分别分配到0-9十个桶中；
- 2.从个位为0的桶开始依据每个元素的十位将元素分配到0-9十个桶中；
- 3.每次依据的位数增加一位（百位，千位，万位），直到集合中最大的数的位数为止；
- 4.最后一次分配完成后从第0个桶开始依次取出元素，直到所有的元素被取出来，这个取出的顺序可以保证元素是从小到大的；
复杂度：每一次散列需要对每个元素进行分配，即n次操作，最多进行最大的数的位数轮散列分配，即k轮，所以时间复杂度为O(n*k)。基数排序需要n+m个额外空间，其中n为待排序集合大小，m为10（无负数元素）或20（有负数元素）
稳定性：基数排序不会破坏相等元素的相对顺序，所以是稳定的

template<class T>
void radixSort(T& cap,int place) {	
    for (int i = 0,num=1; i < place; i++,num*=10) {//num指示对哪一位进行基数排序
        vector<vector<int>> tempVec(10);//二维数组，内部vector的大小看数据量 
        for (int i = 0; i < cap.size(); i++)
        {
            int index = cap[i] / num % 10;
            tempVec[index].push_back(cap[i]);
        }
        cap.clear();		//清除里面的数据
        for (int i = 0; i < 10; i++)		//放回vec
        {
            auto it = tempVec[i].begin();
            while (it != tempVec[i].end())
            {
                cap.push_back(*it);
                ++it;
            }
        }
    }
}

1.8 归并排序**

基本思想：归并排序是建立在归并操作上的一种有效，稳定的排序算法，该算法是采用分治法Divide and Conquer的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。作为一种典型的分而治之思想的算法应用，归并排序的实现由两种方法：一是自上而下的递归（所有递归的方法都可以用迭代重写，所以就有了第 2 种方法）；二是自下而上的迭代；
- 1.申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列；
- 2.设定两个指针，最初位置分别为两个已经排序序列的起始位置；
- 3.比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置；
- 4.重复步骤 3 直到某一指针达到序列尾；
- 5.将另一序列剩下的所有元素直接复制到合并序列尾。
复杂度：很明显归并排序需要logn轮合并，每轮合并需要n-1~n/2次比较，所以时间复杂度为O(nlogn).归并排序比较占用内存，但却是一种效率高且稳定的算法，其需要临时空间存储归并后的数据，因此空间复杂度为O(N)
稳定性：归并排序的合并操作并不会影响相同元素的相对顺序，故稳定。

template<class T>
void mergeSort(T& cap)
{//使用迭代实现二路归并排序
    int len = cap.size();
    if (len == 0 || len == 1)
        return;
    vector<int>tmp(len);       //合并空间
    for (int i = 1; i < len; i *= 2)
    {   //logn趟合并
        int index = 0;
        for (int j = 0; j < len;)
        {
            //合并相邻两子序列
            int next = j + i;
            int k = j;
            while(k <(j+i) && k<len && next < len && next < (j+2*i) )
            {
                if (cap[k] <= cap[next])
                {
                    tmp[index] = cap[k];
                    k++;
                }
                else
                {
                    tmp[index] = cap[next];
                    next++;
                }
                index++;
            }
            while (k<len &&k < j + i)
            {
                tmp[index] = cap[k];
                index++;
                k++;
            }
            while (next < len && next < j + 2 * i)
            {
                tmp[index] = cap[next];
                index++;
                next++;
            }
            j = next;
        }
        copy(tmp.begin(), tmp.end(), cap.begin());
    }
}

1.9 计数排序

基本思想：计数排序的核心在于将输入的数据值转化为键存储在额外开辟的数组空间中。作为一种线性时间复杂度的排序，计数排序要求输入的数据必须是有确定范围的整数。当输入的元素是n个0到k之间的整数时，它的运行时间是Θ(n + k)。计数排序不是比较排序，排序的速度快于任何比较排序算法。由于用来计数的数组C的长度取决于待排序数组中数据的范围（等于待排序数组的最大值与最小值的差加上1），这使得计数排序对于数据范围很大的数组，需要大量内存，因此堆数据范围很大的不适用，该排序算法最号应用于数据范围不大重复值多的情况。例如：计数排序是用来排序0到100之间的数字的最好的算法，但是它不适合按字母顺序排序人名。但是，计数排序可以用在基数排序中的算法来排序数据范围很大的数组。
- 找出待排序的数组中最大和最小的元素；
- 遍历数组cap，对值i作为cap的下标存入+1,即C[i]++;
- 对所有的重复值计数累加
- 从前往后遍历数组C，将对应的下标index作为值存人cap，并在C[index]-1
复杂度：计数排序的时间复杂度与待排序元素的范围相关，其时间复杂度为O(n+k),其中n为元素数量，k为元素的范围（即最大的元素与最小的元素的差加1）。计数排序需要额外开辟k个桶的空间，所以空间复杂度为(k)。
稳定性：计数排序是一个非基于比较的线性时间排序算法,所以看出是一种稳定排序

template<class T>
void countingSort(T& cap)
{
    int len = cap.size();
    if (len == 0 || len == 1)
        return;
    int maxValue = getMaxValue(cap)+1;
    vector<int> tmp(maxValue);
    for (auto i : cap)
        tmp[i]++;
    int _index=0;
    for (int i = 0; i < maxValue; i++)
    {
        while (tmp[i])
        {
            cap[_index] = i;
            tmp[i]--;
            _index++;
        }
    }
}

1.10 桶排序*

基本思想：桶排序是计数排序的升级版。它利用了函数的映射关系，高效与否的关键就在于这个映射函数的确定。为了使桶排序更加高效，我们需要做到这两点：一是在额外空间充足的情况下，尽量增大桶的数量；二是使用的映射函数能够将输入的 N 个数据均匀的分配到 K 个桶中。同时，对于桶中元素的排序，选择何种比较排序算法对于性能的影响至关重要。
- 1.开辟m大小的空间，生成m个桶，每个桶对应一个范围；
- 2.将待排序的所有元素依次按照范围散列到对应的桶里；
- 3.对所有的桶内的元素以桶为单位排序；
- 4.从第一个桶开始依次将排好序的元素取出；
复杂度：对于待排序序列大小为N，共分为M个桶，N次循环，将每个元素装入对应的桶中。M次循环，对每个桶中的数据进行排序（平均每个桶有N/M个元素）。一般使用较为快速的排序算法，时间复杂度为 O(N/MlogN/M)，整个桶排序的时间复杂度为：O(N)+O(M∗(N/M∗log(N/M))) = O(N)+O(N∗(log(N/M)) = O(N)+O(C）= O(N∗(log(N/M)+1))；桶排序需要额外的m个桶的空间和n个元素的空间，故空间复杂度为O(m+n)。
稳定性：桶排序的稳定性取决于桶内排序使用的算法，所以我们通常认为桶排序是稳定排序。