排序算法

稳定：如果a原本在b前面，而a=b，排序之后a仍然在b的前面。

排序方法	时间复杂度（平均）	时间复杂度（最坏）	时间复杂度（最好）	空间复杂度	稳定性
插入排序	O()	O()	O()	O()	稳定
希尔排序	O()	O()	O()	O()	不稳定
选择排序	O()	O()	O()	O()	不稳定
堆排序	O()	O()	O)	O()	不稳定
冒泡排序	O()	O()	O()	O()	稳定
快速排序	O()	O()	O()	O()	不稳定
归并排序	O()	O()	O()	O()	稳定

计数排序	O()	O()	O()	O()	稳定
桶排序	O()	O()	O()	O()	稳定
基数排序	O()	O()	O()	O()	稳定

冒泡排序

冒泡排序是一种简单的排序算法。它重复地走访过要排序的数列，一次比较两个元素，如果它们的顺序错误就把它们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。

算法描述

比较两个相邻的元素，如果第一个比第二个大，那么就交换他们的位置。
重复步骤（1）的操作，依次比较两两相邻的两个元素。所有元素对比过后表示一次循环结束。
至多循环n-1次，重复上面两个步骤。
直到没有任何一组元素需要交换位置表示排序完成。

算法图解

C++代码

void BubbleSort(int* slist,int length)
{
    int temp;
    for (int i = 0; i < length - 1; i++)
    {
        for (int j = 0; j < length - 1 - i; j++)
        {
            if (slist[j] > slist[j + 1])
            {
                temp = slist[j];
                slist[j] = slist[j + 1];
                slist[j + 1] = temp;
            }
        }
    }
}

算法复杂度

最好的情况为正序，只需要一遍遍历，所以时间复杂度为O(n)，最坏的情况为逆序，需要遍历次，所以时间复杂度为O()。由于只有一个交换的变量temp需要内存，所以空间复杂度为O(1)。该算法稳定

选择排序

选择排序(Selection-sort)是一种简单直观的排序算法。它的工作原理：首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。

算法描述

遍历整个列表N个元素，找到最小的元素，与第一个元素交换位置。
遍历剩余的N-1个元素，找到最小的元素，将它排在剩余N-1个元素的第一个。
以此类推，重复步骤（2），直到N-1小于1。

算法图解

C++代码

void SelectSort(int* slist, int length)
{
    int min;
    int temp;
    for (int i = 0; i < length; i++)
    {
        min = i;
        for (int j = i + 1; j < length; j++)
        {
            if (slist[j] < slist[min])        // 寻找最小的数
            {
                min = j;                      // 将最小数的索引保存
            }
        }
        temp = slist[i];
        slist[i] = slist[min];
        slist[min] = temp;
    }
}

算法复杂度

不管最后还是最坏的情况，选择排序的时间复杂度都是O()，空间复杂度为O(1)。该算法不稳定。

插入排序

插入排序（Insertion-Sort）的算法描述是一种简单直观的排序算法。它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。

算法描述

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

算法图解

C++代码

void InsertSort(int* slist,int length)
{
    for (int i = 1; i < length; i++)
    {
        int preIndex = i - 1;
        int number = slist[i];                //记录要进行插入的值
        while (preIndex >= 0 && slist[preIndex] > number)
        {
            slist[preIndex+1] = slist[preIndex];        //将插入值大的数进行后移，会有两个一样的值，后续直接覆盖掉
            preIndex--;
        }
        slist[preIndex+1] = number;            //preIndex为插入位置的前一个索引，当到达边界时preIndex为-1，此时会插入头部
    } 
}

算法复杂度

最好的情况为正序，只需要一遍遍历，所以时间复杂度为O(n)，最坏的情况为逆序，需要遍历次，所以时间复杂度为O()。空间复杂度为O(1)。该算法稳定

希尔排序

希尔排序，也称递减增量排序算法。将整个列表根据增量分为若干个子列表分别进行插入排序。随着增量的减小，列表趋于基本有序，当增量为1时，相当再做一次插入排序，使列表有序。

算法描述

选择一个增量gap，一般为列表长度的一半。
将列表中元素下标每隔gap的元素组成一个新的子列表。
对每个子列表进行插入排序。
将gap去原来的一半，重复步骤2、3，直到gap小于1。

算法图解

C++代码

void ShellSort(int* slist, int length)
{
    int temp;
    //gap为增量，一般取长度的一般
    int gap = length / 2;
    //当增量小于1时结束排序
    while (gap >= 1)
    {
        //最多分为gap个列表
        for (int i = 0; i < gap; i++)
        {
            //下面的代码为一个简单的插入排序，只是插入排序的数组下标每次移动的不是1而是gap
            for (int j = i+gap; j < length; j = j + gap)
            {
                if (slist[j] < slist[j-gap])
                {
                    int k = j - gap;
                    int temp = slist[j];
                    while (k >= 0 && slist[k] > temp)
                    {
                        slist[k + gap] = slist[k];
                        k = k - gap;
                    }
                    slist[k+gap] = temp;
                }
            }
        }
        //增量递减
        gap = gap/ 2;
    }
}

算法复杂度

希尔排序是不稳定的排序，它时间复杂度和步长的选择有关。

n/2、n/4、n/8…1

该序列称为希尔增量序列，使用希尔增量时，希尔排序在最坏情况下的时间复杂度为O()。

1、3、7…2^k-1

该序列序列称为Hibbard增量序列，使用Hibbard增量时，希尔排序在最坏情况下的时间复杂度为O()。

归并排序

归并排序采用分治的思想，将一个列表分为多个子列表，每个子序列是有序的。然后再把有序子序列合并为整体有序序列。

算法描述

将列表元素对半分开，分为两个列表。
重复步骤 1 ，直至每个列表只有一个元素。
将两个相邻的列表排序，直至整个列表有序。

算法图解

C++代码

//排序
void MergeSort(int sourceArr[], int tempArr[], int startIndex, int midIndex, int endIndex)
{
    //i:第一个待排序的起始位置，
    int i = startIndex;
    //j:第二个待排序的起始位置，
    int j = midIndex + 1;
    int k = startIndex;

    while (i != midIndex + 1 && j != endIndex+1)
    {
        if (sourceArr[i] > sourceArr[j])
        {
            tempArr[k] = sourceArr[j];
            k++;
            j++;
        }
        else
        {
            tempArr[k] = sourceArr[i];
            k++;
            i++;
        }    
    }
    //将两个中未排序的添加到tempArr中
    while (i != midIndex + 1)
    {
        tempArr[k] = sourceArr[i];
        i++;
        k++;
    }
    //将两个中未排序的添加到tempArr中
    while (j != endIndex+1)
    {
        tempArr[k] = sourceArr[j];
        j++;
        k++;
    }

    //将tempArr中的元素赋值给sourceArr
    for (int i = startIndex; i <= endIndex; i++)
    {
        sourceArr[i] = tempArr[i];
    }
}

//分解递归
void BranchSort(int sourceArr[], int tempArr[], int startIndex, int endIndex)
{
    if (startIndex < endIndex)
    {
        int mid = startIndex + (endIndex - startIndex) / 2;
        BranchSort(sourceArr, tempArr, startIndex, mid);
        BranchSort(sourceArr, tempArr, mid+1, endIndex);
        MergeSort(sourceArr, tempArr, startIndex, mid, endIndex);
    }
}

算法复杂度

归并排序是稳定排序算法，假设数组长度为n，那么拆分数组共需logn, 又每步都是一个普通的合并子数组的过程，时间复杂度为O(n)，故其综合时间复杂度为O(nlogn)。另一方面，归并排序多次递归过程中拆分的子数组需要保存在内存空间，其空间复杂度为O(n)。

快速排序

快速排序采用分治的思想，通通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

算法描述

选定一个基准元素
从右往左找到比基准元素小的元素
从左往右找到比基准元素大的元素
交换左右找到的两个元素的位置
重复上面2、3、4步，直至左右两个元素相遇。

算法图解

C++代码

void QuickSort(int* slist, int left, int right)
{
    if (left >= right)
    {
        return;
    }
    int i = left;
    int j = right;
    int key = slist[left];
    int temp;

    //直到遍历完整个列表
    while (i < j)
    {
        //从右到左找到小于key的下标
        while (i<j&&slist[j] >= key)
        {
            j--;
        }
        //从左到右找到大于key的下标
        while (i<j && slist[i] <= key)
        {
            i++;
        }
        //交换找到的两个元素,保证小的元素在前，大的元素在后
        if (i < j)
        {
            temp = slist[i];
            slist[i] = slist[j];
            slist[j] = temp;
        }
    }
    //将key元素交换到中间，确保分为大小两个列表
    temp = slist[left];
    slist[left] = slist[j];
    slist[j] = temp;
    QuickSort(slist, left, j - 1);
    QuickSort(slist, j + 1, right);
}

算法复杂度

快速排序之所比较快，因为相比冒泡排序，每次交换是跳跃式的。每次排序的时候设置一个基准点，将小于等于基准点的数全部放到基准点的左边，将大于等于基准点的数全部放到基准点的右边。
这样在每次交换的时候就不会像冒泡排序一样每次只能在相邻的数之间进行交换，交换的距离就大的多了。因此总的比较和交换次数就少了，速度自然就提高了。
当然在最坏的情况下，仍可能是相邻的两个数进行了交换。因此快速排序的最差时间复杂度和冒泡排序是一样的都是O()，它的平均时间复杂度为O(nlogn)。

堆排序

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

完全二叉树的特点：

叶子结点只能出现在最下两层。
最下层的叶子一定集中在左部连续位置
倒数二层，若有叶子结点，一定都在右部连续位置。
如果结点度为1，则该结点只有左孩子，即不存在只有右子树的情况。
同样结点数的二叉树，完全二叉树的深度最小。
‌完全二叉树的深度‌：具有个节点的完全二叉树的深度为
‌编号规则‌：具有个节点的完全二叉树，按顺序编号，节点的父节点为，左子节点为，右子节点为

要想学习堆排序，首先需要了解两种调整算法：

堆的向上调整算法

堆的向上调整算法是实现堆的插入核心算法。

对于堆的建立，假设我们将一组数据一个一个的加入到堆中，那么我们需要在每一个元素入堆时都要进行调整，我们将加入的元素存入到顺序表的最后，然后利用双亲结点和孩子结点之间的关系来判断是否需要调整，知道调整到根节点为止。对于此算法思想既可以使用递归算法，也可以使用循环算法，如下：

void AdjustUp(HPDataType* a, int child) {
	int parent = (child - 1) / 2;                    //index从0开始，所以减1，从1开始则是 child / 2
	while (child > 0) {
		//建立小堆，若建大堆，将 < 改为 >
		if (a[child] < a[parent]) {
			Swap(&a[child], &a[parent]);
			child = parent;
			parent = (child - 1) / 2;
		}
		else {
			break;
		}
	}
}

堆的向下调整算法

向下调整算法是堆删除堆顶元素的核心算法。

当我们需要将堆顶的元素弹出时，将整个堆进行维护，建立一个新的堆。其主要思路是将当前元素的孩子结点与双亲结点进行比较，但是此时双亲节点的孩子节点有两个，我们需要找出最合适的那一个，比如：建小堆则找出最小的孩子结点，建大堆则找出最大的孩子结点。然后将孩子结点与双亲结点进行交换，以此迭代，直到迭代到叶子结点。

//建小堆的向下调整算法
void AdjustDown(HPDataType* a, int size, int parent) {
    //左孩子结点与双亲结点的关系
	int child = parent * 2 + 1;                //index从0开始，所以加1，从1开始则是 parent * 2
    //假若右孩子比左孩子更小，则将child变量加一。child + 1 <size 用于保证不会越界
	//若建大堆，改为if ((a[child + 1] > a[child]) && (child + 1) < size)
    if ((a[child + 1] < a[child]) && (child + 1) < size) {
		++child;
	}
    //当child>=size时表示已经到达叶子结点跳出循环
	while (child<size) {
        //双亲结点大于孩子结点交换
        //若建大堆，改为if (a[parent] < a[child])
		if (a[parent] > a[child]) {
			Swap(&a[parent], &a[child]);
            //进行迭代
			parent = child;
			child = parent * 2 + 1;
			if ((a[child + 1] < a[child]) && (child + 1) < size) {
				++child;
			}
		}
        //若双亲结点不在大于孩子结点，说明已经迭代结束，不在需要继续进行迭代
		else {
			break;
		}
	}
}

算法描述

堆排序的步骤分为三步:

建堆（升序建大堆，降序建小堆），每次将堆顶元素与最大或最小的叶子节点交换，并调整为最大或最小堆
交换数据，建完堆之后堆顶元素为最大或最小值，将其与未排序的末尾元素交换。
向下调整。交换完成后堆顶进入有序队列（等于删除），使用向下调整，继续调整为最大或最小堆

可以将整个堆压扁到叶子节点这一层，形成一个数组，便于理解。

算法图解

C++代码

// 堆排序
/*
大顶堆sort之后，数组为从小到大排序
*/
//====调整=====
void AdjustHeap(int *h, int node, int len) //----node为需要调整的结点编号，从0开始编号;len为堆长度
{
    int index = node;
    int child = 2 * index + 1; // 左孩子，第一个节点编号为0，index从0开始，所以加1，从1开始则是 2 * index
    while (child < len)
    {
        // 右子树
        if (child + 1 < len && h[child] < h[child + 1])
        {
            child++;
        }
        if (h[index] >= h[child])
            break;
        Swap(h[index], h[child]);
        index = child;
        child = 2 * index + 1;
    }
}

//====建堆=====
void MakeHeap(int *h, int len)
{
    for (int i = len / 2; i >= 0; --i)
    {
        AdjustHeap(h, i, len);
    }
}

//====排序=====
void HeapSort(int *h, int len)
{
    MakeHeap(h, len);
    for (int i = len - 1; i >= 0; --i)
    {
        Swap(h[i], h[0]);
        AdjustHeap(h, 0, i);
    }
}

算法复杂度

堆排序使用堆来选数，效率就高了很多。时间复杂度：O(N*logN)；空间复杂度：O(1)；稳定性：不稳定

计数排序

计数排序不是基于比较的排序算法，其核心在于将输入的数据值转化为键存储在额外开辟的数组空间中。
它的基本思想是，对于待排序的数组，遍历数组元素，统计每个元素出现的次数，然后根据次数输出排序后的数组。
作为一种线性时间复杂度的排序，计数排序要求输入的数据必须是有确定范围的整数。

算法描述

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

算法图解

C++代码

vector<int> countingSort(vector<int> arr, int maxValue) {
    // 创建一个大小为maxValue + 1的桶，并初始化为0
    vector<int> bucket(maxValue + 1, 0);
    vector<int> sortedArr; // 用于存储排序后的数组

    // 统计每个值出现的次数
    for (int i = 0; i < arr.size(); ++i) {
        bucket[arr[i]]++;
    }

    // 根据桶中的数据重建排序后的数组
    for (int j = 0; j <= maxValue; ++j) {
        while (bucket[j] > 0) {
            sortedArr.push_back(j);
            bucket[j]--;
        }
    }
    return sortedArr;
}

算法复杂度

计数排序是一个稳定的排序算法。当输入的元素是 n 个 0到 k 之间的整数时，时间复杂度是O(n+k)，空间复杂度也是O(n+k)，其排序速度快于任何比较排序算法。当k不是很大并且序列比较集中时，计数排序是一个很有效的排序算法。

桶排序

桶排序是计数排序的升级版。它利用了函数的映射关系，高效与否的关键就在于这个映射函数的确定。

桶排序 (Bucket sort)的工作的原理：假设输入数据服从均匀分布，将数据分到有限数量的桶里，每个桶再分别排序（有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排）。

算法描述

设置一个定量的数组当作空桶；
遍历输入数据，并且把数据一个一个放到对应的桶里去；
对每个不是空的桶进行排序；
从不是空的桶里把排好序的数据拼接起来。

算法图解

C++代码

// 插入排序辅助函数
void insertionSort(std::vector<int>& arr) {
    for (size_t i = 1; i < arr.size(); ++i) {
        int key = arr[i];
        int j = i - 1;
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            --j;
        }
        arr[j + 1] = key;
    }
}

// 桶排序主函数
std::vector<int> bucketSort(std::vector<int> arr, int bucketSize = 5) {
    if (arr.empty()) return arr;

    int minValue = *std::min_element(arr.begin(), arr.end());
    int maxValue = *std::max_element(arr.begin(), arr.end());

    // 计算桶的数量
    size_t bucketCount = (maxValue - minValue) / bucketSize + 1;
    std::vector<std::vector<int>> buckets(bucketCount);

    // 分配输入数组到各个桶中
    for (int num : arr) {
        buckets[(num - minValue) / bucketSize].push_back(num);
    }

    // 清空原始数组并按序合并已排序的桶
    arr.clear();
    for (auto& bucket : buckets) {
        insertionSort(bucket); // 对每个桶进行排序
        arr.insert(arr.end(), bucket.begin(), bucket.end());
    }

    return arr;
}

算法复杂度

当桶的数量和需要排序的元素一样多，桶排序此时就变成了计数排序，桶排序最好情况下使用线性时间O(n)，桶排序的时间复杂度，取决与对各个桶之间数据进行排序的时间复杂度，因为其它部分的时间复杂度都为O(n)。很显然，桶划分的越小，各个桶之间的数据越少，排序所用的时间也会越少。但相应的空间消耗就会增大。

基数排序

基数排序（Radix Sort）是按照低位先排序，然后收集；再按照高位排序，然后再收集；依次类推，直到最高位。有时候有些属性是有优先级顺序的，先按低优先级排序，再按高优先级排序。最后的次序就是高优先级高的在前，高优先级相同的低优先级高的在前。

基数排序可以分为两种：LSD(低位到高位排序)，MSD(高位到低位排序)，LSD的基数排序适用于位数少的数列，如果位数多的话，使用MSD的效率会比较好。

LSD

算法描述

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

算法图解

C++代码

/********************************************************
*函数名称：GetNumInPos
*参数说明：num 一个整形数据
*     pos 表示要获得的整形的第pos位数据
*说明：    找到num的从低到高的第pos位的数据
*********************************************************/
int GetNumInPos(int num, int pos)
{
	int temp = 1;
	for (int i = 0; i < pos - 1; i++)
		temp *= 10;
 
	return (num / temp) % 10;
}
 
#define MAXPOS 10    //最高位的位数
void RadixSort(vector<int> &A)
{
	int len = A.size();
	vector<vector<int>> radixArray(10);  //分为0~9的序列空间
 
	for (int pos = 1; pos <= MAXPOS; pos++)    //从个位开始到最高位数
	{
		for (int i = 0; i < len; i++)    //分配过程
		{
			int num = GetNumInPos(A[i], pos);
			radixArray[num].push_back(A[i]);
		}
 
		for (int i = 0, j = 0; i < 10; i++)    //收集
		{
			while (!radixArray[i].empty())
			{
				A[j++] = radixArray[i].front();  //取首部数据依次插入原数组
				radixArray[i].erase(radixArray[i].begin());    //移除首部元素
			}
		}
	}
}

MSD

MSD基数排序是从最高位开始对序列进行分组，到最低位为止。但是其实现过程是和LSD基数排序不同的，排序过程中需要用到递归函数。

算法描述

MSD的方式由高位数为基底开始进行分配，但在分配之后并不马上合并回一个数组中，而是在每个“桶子”中建立“子桶”，将每个桶子中的数值按照下一数位的值分配到“子桶”中。在进行完最低位数的分配后再合并回单一的数组中。

算法图解

C++代码

/********************************************************
 *函数名称：GetNumInPos
 *参数说明：num 一个整形数据
 *     pos 表示要获得的整形的第pos位数据
 *说明：    找到num的从低到高的第pos位的数据
 *********************************************************/
int GetNumInPos(int num, int pos)
{
    int temp = 1;
    for (int i = 0; i < pos - 1; i++)
        temp *= 10;
    return (num / temp) % 10;
}
// MSD,调用时指定最高位数d
void RadixSort(vector<int> &A, int d)
{
    int len = A.size();
    vector<vector<int>> radixArray(10); // 分为0~9的序列空间，用队列保存每个桶分配的数据
    // 位数大于0，且数组长度大于1
    if (d >= 1 && len > 1)
    {
        for (int i = 0; i < len; i++) // 分配过程
        {
            int num = GetNumInPos(A[i], d);
            radixArray[num].push_back(A[i]);
        }
        cout << endl;
        for (int i = 0, j = 0; i < 10; i++) // 收集
        {
            RadixSort(radixArray[i], d - 1); // 递归,对每个子桶从次高位开始分配
            while (!radixArray[i].empty())
            {
                A[j++] = radixArray[i].front(); // 取队列首部数据依次插入原数组
                radixArray[i].erase(radixArray[i].begin());
            }
        }
    }
}

算法复杂度

基数排序基于分别排序，分别收集，所以是稳定的。但基数排序的性能比桶排序要略差，每一次关键字的桶分配都需要O(n)的时间复杂度，而且分配之后得到新的关键字序列又需要O(n)的时间复杂度。假如待排数据可以分为d个关键字，则基数排序的时间复杂度将是O(d*2n) ，当然d要远远小于n，因此基本上还是线性级别的。

基数排序的空间复杂度为O(n+k)，其中k为桶的数量。一般来说n>>k，因此额外空间需要大概n个左右。