常用排序算法比较

排序方法 平均时间复杂度 最坏时间复杂度 最好时间复杂度 空间复杂度 稳定性 复杂性
插入排序 O(n2) O(n2) O(n) O(1) 稳定 简单
希尔排序 O(n1.3) O(1) 不稳定 较复杂
冒泡排序 O(n2) O(n2) O(n) O(1) 稳定 简单
快速排序 O(nlog2n) O(n2) O(nlog2n) O(log2n) 不稳定 较复杂
选择排序 O(n2) O(n2) O(n2) O(1) 不稳定 简单
堆排序 O(nlog2n) O(nlog2n) O(nlog2n) O(1) 不稳定 较复杂
归并排序 O(nlog2n) O(nlog2n) O(nlog2n) O(n) 稳定 较复杂
基数排序 O(d(n+r)) O(d(n+r)) O(d(n+r)) O(r) 稳定 较复杂





堆排序

堆排序（Heapsort）是利用堆这种数据结构所设计的一种排序算法

基本步骤：

  1. 首先将数组构建成一个小顶堆（或大顶堆）

  2. 从堆顶nums[0]取出最小值（或最大值）放到数组后端nums[n]处，然后将nums[0]重新调整为小顶堆（或大顶堆）,再将nums[0]与nums[n-1]….

  3. 重复步骤2，直到整个数组都有序（堆的大小为1时）。

时间复杂度

O(nlog2n)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
//调整函数
void mHeap(vector<int>& nums,int start, int end) {
	int l, r;

	while (start*2+1 <= end) {
			l = start * 2 + 1;
		r = start * 2 + 2;
		if (r <= end && nums[l] < nums[r])//将标志位设置为左右子节点中最大（小）的
			l = r;
		if (nums[start] > nums[l]) {//当节点大于左右子节点的值时停止
			break;
		}
		swap(nums[start], nums[l]);
		start = l;
	}
}

void HeapSort(vector<int>& nums, int size) {

	//将数组构建成为一个大顶堆
	for (int i = size / 2 - 1; i >= 0; --i) {//从倒数第二层开始，到根节点为止
		mHeap(nums, i, size - 1);
	}

	//不断将堆顶元素移至堆底，并将堆的大小-1，当堆的大小为1时，排序完成
	for (int i = size - 1; i > 0; --i) {
		swap(nums[i], nums[0]);
		mHeap(nums, 0, i - 1);
	}
}





快速排序

快速排序是分而治之思想在算法上的典型应用，快速排序使用分治法策略把一个串行（list）分为两个子串行（sub-list）。

基本步骤：

  1. 将第i个元素作为基准（pivot）

  2. 重新排序数列，所有元素比基准值小的放在基准前面，所有比基准值大的放在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作

  3. 递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序；

动态图片演示

时间复杂度

最好情况O(nlog2n)：

Partition 每次恰好能均分序列，其递归树的深度就为.log2n.+1（.x.表示不大于x的最大整数），即仅需递归log2n次

最坏情况O(n2):

每次划分只能将序列分为一个元素与其他元素两部分，这时的快速排序退化为冒泡排序 (如待排序数组已经有序)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
void quicksort(vector<int>& nums,int left,int right) {
	//Partition Begin
	int  pivot;
	int i = left, j = right;
	
	pivot = nums[i];

	while (i != j) {
		while (i < j && nums[j] >= pivot)//此处须使用>=（如果使用>可能在两侧都等于pivot时产生死循环）
			--j;
		if (i < j) {
			nums[i] = nums[j];
		}
		while (i < j && nums[i] <= pivot)
			++i;
		if (i < j) {
			nums[j] = nums[i];
		}
	}
	nums[i] = pivot;
    //Partition End

	if (left < i-1)//递归在左右子分区调用
		quicksort(nums, left, i-1);
	if (i+1 < right)
		quicksort(nums, i+1, right);
}





归并排序

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



归并排序的实现分为两种：

  • 自上而下的递归 （所有递归的方法都可以用迭代重写，所以就有了第 2 种方法）
  • 自下而上的迭代

动态图片演示

算法步骤：

  1. 申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列

  2. 设定两个指针，最初位置分别为两个已经排序序列的起始位置

  3. 比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置

  4. 重复步骤3，直到某一指针达到序列尾

  5. 将另一序列剩下的所有元素直接复制到合并序列尾


时间复杂度

O(nlog2n)


由上至下的递归

示例：

自上而下归并示例

通过”从上往下的归并排序”来对数组{80,30,60,40,20,10,50,70}进行排序时：

  1. 将数组{80,30,60,40,20,10,50,70}看作由两个有序的子数组{80,30,60,40}和{20,10,50,70}组成。对两个有序子树组进行排序即可。
  2. 将子数组{80,30,60,40}看作由两个有序的子数组{80,30}和{60,40}组成。
    将子数组{20,10,50,70}看作由两个有序的子数组{20,10}和{50,70}组成。
  3. 将子数组{80,30}看作由两个有序的子数组{80}和{30}组成。
    将子数组{60,40}看作由两个有序的子数组{60}和{40}组成。
    将子数组{20,10}看作由两个有序的子数组{20}和{10}组成。
    将子数组{50,70}看作由两个有序的子数组{50}和{70}组成。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
void mergeSort(vector<int>& nums, int start, int end) {
	int mid;

	if (nums.empty() || start >= end)//当数列为空或者切分为单个元素的数列时，终止切分
		return;
	mid = (start + end) / 2;
	mergeSort(nums, start, mid);//递归切分
	mergeSort(nums, mid + 1, end);z
	merge(nums, start, mid, end);
}

void merge(vector<int>& nums, int start, int mid, int end) {
	vector<int> temp;
	int i = start, j = mid + 1;

	while (i <= mid && j <= end) {//依次将两个有序数列中较小的数加入到临时向量中
		if (nums[i] < nums[j])
			temp.push_back(nums[i++]);
		else
			temp.push_back(nums[j++]);
	}
	while (i <= mid)
		temp.push_back(nums[i++]);
	while (j <= end)
		temp.push_back(nums[j++]);
	for (int p = 0; p < temp.size(); ++p) {//将排序后的数列从临时向量中转移回去
		nums[start + p] = temp[p];
	}
}

由下至上的迭代

示例：

自下而上归并示例

通过”从下往上的归并排序”来对数组{80,30,60,40,20,10,50,70}进行排序时：

  1. 将数组{80,30,60,40,20,10,50,70}看作由8个有序的子数组{80},{30},{60},{40},{20},{10},{50}和{70}组成。
  2. 将这8个有序的子数列两两合并。得到4个有序的子树列{30,80},{40,60},{10,20}和{50,70}。
  3. 将这4个有序的子数列两两合并。得到2个有序的子树列{30,40,60,80}和{10,20,50,70}。
  4. 将这2个有序的子数列两两合并。得到1个有序的子树列{10,20,30,40,50,60,70,80}。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
void merge(vector<int>& nums, int start, int mid, int end) {
	vector<int> temp;
	int i = start, j = mid + 1;

	while (i <= mid && j <= end) {//依次将两个有序数列中较小的数加入到临时向量中
		if (nums[i] < nums[j])
			temp.push_back(nums[i++]);
		else
			temp.push_back(nums[j++]);
	}
	while (i <= mid)
		temp.push_back(nums[i++]);
	while (j <= end)
		temp.push_back(nums[j++]);
	for (int p = 0; p < temp.size(); ++p) {//将排序后的数列从临时向量中转移回去
		nums[start + p] = temp[p];
	}
}

/*对数组a做若干次合并：数组a的总长度为len，将它分为若干个长度为gap的子数组；
 *             将"每2个相邻的子数组" 进行合并排序。
 *
 * 参数说明：
 *     a -- 待排序的数组
 *     len -- 数组的长度
 *     gap -- 子数组的长度
 */
void mergeGroups(int* a, int len, int gap)
{
    int i;

    // 将"每2个相邻的子数组" 进行合并排序。
    for(i = 0; i+2*gap-1 < len; i+=(2*gap))
    {
        merge(a, i, i+gap-1, i+2*gap-1);
    }

    // 若 i+gap-1 < len-1，则剩余一个子数组没有配对。
    // 将该子数组合并到已排序的数组中。
    if ( i+gap-1 < len-1)
    {
        merge(a, i, i + gap - 1, len - 1);
    }
}

/*
 * 归并排序(从下往上)
 *
 * 参数说明：
 *     a -- 待排序的数组
 *     len -- 数组的长度
 */
void mergeSortDown2Up(int* a, int len)
{
    int n;

    if (a==NULL || len<=0)
        return ;

    for(n = 1; n < len; n*=2)
        mergeGroups(a, len, n);
}





冒泡排序

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

算法步骤：

  1. 比较相邻的元素。如果第一个比第二个大，就交换他们两个。

  2. 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。

  3. 针对所有的元素重复以上的步骤，除了最后一个。

  4. 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

动态图片演示

时间复杂度

最好情况O(n)：

数组是正序时

最坏情况O(n2):

数组是反序时

1
2
3
4
5
6
void bubble_sort(vector<int>& n){
	for(int i = 1; i < n.size() - 1 ; ++i)
		for(int j = 0; j < n.size() - i; ++j)
			if(n[j] > n[j + 1])
				swap(n[j], n[j + 1]);
}





选择排序

选择排序是一种简单直观的排序算法，无论什么数据进去都是 O(n²) 的时间复杂度

算法步骤：

  1. 首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置。
  2. 再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。
  3. 重复第二步，直到所有元素均排序完毕。

动态图片演示

时间复杂度

O(n2)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
//选择排序
void select_sort(int arr[], int n){
	int i;        //有序区的末尾位置
	int j;        //无序区的起始位置
	int min;      //无序区中的最小元素位置

	for(i = 0; i < n; ++i){
		min = i;
		
		//找出"arr[i+1] ... arr[n]"之间的最小元素的位置，并赋值给min
		for(j = i+1; j < n; ++j){
			if(arr[j] < a[min])
				min = j;
		}
		
		//交换arr[i]和arr[min]，交换之后保证了arr[0] ... arr[i]之间的元素是有序的
		if(min != i){
				swap(arr[i], arr[min]);
		}
	}
}





插入排序

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

算法步骤：

  1. 将待排序序列第一个元素看做一个有序序列，把第二个元素到最后一个元素当成是未排序序列。
  2. 从头到尾依次扫描未排序序列，将扫描到的每个元素插入有序序列的适当位置。（如果待插入的元素与有序序列中的某个元素相等，则将待插入元素插入到相等元素的后面。）

动态图片演示

时间复杂度

最坏情况O(n2):

插入第2个元素时要考察前1个元素，插入第3个元素时，要考虑前2个元素，……，插入第N个元素，要考虑前 N - 1 个元素。因此，最坏情况下的比较次数是 1 + 2 + 3 + … + (N - 1)，等差数列求和，结果为 N2 / 2

最好情况O(n):

数组已经是有序的，每插入一个元素，只需要考查前一个元素，因此最好情况下，插入排序的时间复杂度为O(n)

1
2
3
4
5
6
7
8
9
10
11
12
void InsertSort(int array[], int len) {
	for (int i = 1; i < len; i++) {
		int j = i-1;
		int temp = array[i];
		while (j >= 0 && array[j] > temp) {//此处实现为从右至左，即i-1到0）
			array[j + 1] = array[j];
			j--;
		}
		if (j != i - 1)
			array[j + 1] = temp;
	}
}





希尔排序

希尔排序，也称递减增量排序算法，是插入排序的一种更高效的改进版本。但希尔排序是不稳定的。

希尔排序是基于插入排序的以下两点性质而提出改进方法的：

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

基本思想：

希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止。


算法步骤：

  1. 选择一个增量序列 g1，g2，……gi … gj……，gk，其中 gi > gj, gk = 1；
    按增量序列个数 k，对序列进行 k 趟排序

  2. 每趟排序，根据对应的增量 gi，将待排序列分割成若干长度为 m 的子序列，分别对各子表进行直接插入排序。当增量因子为 1 时，整个序列作为一个表来处理，表长度即为整个序列的长度。


时间复杂度

最好情况O(nsub>1.3)：

采用Hibbard增量序列时


下方代码采用shell增量序列，时间复杂度会高于Hibbard序列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
void shell_sort(vector<int>& n) {
	int gap = n.size() / 2;//构建shell增量序列

	while (gap > 0) {
		int i, j;
		//具体实现时采用跨组处理的方式，即先处理每组i+gap再处理i+gap+gap以此类推... 
		for (i = gap; i < n.size(); i++) {
			j = i - gap;
			int temp = n[i];
			while (j >= 0 && n[j] > temp) {
				n[j + gap] = n[j];
				j -= gap;
			}
			n[j + gap] = temp;
		}
		gap = gap >> 1;
	}
}





计数排序

计数排序的核心在于将输入的数据值转化为键存储在额外开辟的数组空间中。作为一种线性时间复杂度的排序，计数排序要求输入的数据必须是有确定范围的整数。计数排序不是比较排序，排序的速度快于任何比较排序算法

时间复杂度

O(n+k)

n为数组的长度，k为数组中最大整数的值

算法步骤：

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

动态图片演示

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
vector<int> countingSort(vector<int> arr){
	int k = getK(arr);
	int pos = 0;
	vector<int> bucket(k+1,0);
	for(int i = 0; i < arr.size(); i++){
		bucket[arr[i]]++;
	}
	for(int i = 0; i < bucket.size(); i++){
		while(bucket[i] > 0){
			arr[pos++] = i;
			bucket[i]--;
		}
	}
	return arr;
}

int getK(vector<int> arr){
	int largest = arr[0];
	for(int i = 1; i < arr.size(); i++){
		if(arr[i] > largest)
			largest = arr[i];
	}
	return largest;
}





桶排序

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

为了使桶排序更加高效，我们需要做到这两点：

  1. 在额外空间充足的情况下，尽量增大桶的数量

  2. 使用的映射函数能够将输入的 N 个数据均匀的分配到 K 个桶中

同时，对于桶中元素的排序，选择何种比较排序算法对于性能的影响至关重要。

时间复杂度：

O(n + f(n/m))

n为数组的长度，m为桶的数量,f()为对桶中元素进行排序的算法的时间复杂度公式。当n==m时，退化为计数排序

空间复杂度为： max(n, m).

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
const int BUCKET_NUM = 10;//定义桶的大小

struct ListNode{//定义链表节点
        explicit ListNode(int i=0):mData(i),mNext(NULL){}
        ListNode* mNext;
        int mData;
};

ListNode* insert(ListNode* head,int val){//向链表按照插入排序方式插入新节点
        ListNode dummyNode;
        ListNode *newNode = new ListNode(val);
        ListNode *pre,*curr;
        dummyNode.mNext = head;
        pre = &dummyNode;
        curr = head;
        while(NULL!=curr && curr->mData<=val){
                pre = curr;
                curr = curr->mNext;
        }
        newNode->mNext = curr;
        pre->mNext = newNode;
        return dummyNode.mNext;
}


ListNode* Merge(ListNode *head1,ListNode *head2){//归并两个链表
        ListNode dummyNode;
        ListNode *dummy = &dummyNode;
        while(NULL!=head1 && NULL!=head2){
                if(head1->mData <= head2->mData){
                        dummy->mNext = head1;
                        head1 = head1->mNext;
                }else{
                        dummy->mNext = head2;
                        head2 = head2->mNext;
                }
                dummy = dummy->mNext;
        }
        if(NULL!=head1) dummy->mNext = head1;
        if(NULL!=head2) dummy->mNext = head2;
       
        return dummyNode.mNext;
}

void BucketSort(int n,int arr[]){
        vector<ListNode*> buckets(BUCKET_NUM,(ListNode*)(0));//创建桶
        for(int i=0;i<n;++i){
                int index = arr[i]/BUCKET_NUM;//从数组映射到桶
                ListNode *head = buckets.at(index);
                buckets.at(index) = insert(head,arr[i]);
        }
        ListNode *head = buckets.at(0);
        for(int i=1;i<BUCKET_NUM;++i){//依次合并所有桶
                head = Merge(head,buckets.at(i));
        }
        for(int i=0;i<n;++i){//将链表中的数据覆写到数组中
                arr[i] = head->mData;
                head = head->mNext;
        }
}





基数排序

基数排序是一种非比较型整数排序算法，其原理是将整数按位数切割成不同的数字，然后按每个位数分别比较。这样从最低位排序一直到最高位排序完成以后,数列就变成一个有序序列.

由于整数也可以表达字符串（比如名字或日期）和特定格式的浮点数，所以基数排序也不是只能使用于整数。

动态图片演示

时间复杂度

O(d*(n+b))：

d为数组中数字位数的最大值，其中b是数字的进制数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
int maxbit(int data[], int n) //辅助函数，求数据的最大位数
{
    int maxData = data[0];              ///< 最大数
    /// 先求出最大数，再求其位数，这样有原先依次每个数判断其位数，稍微优化点。
    for (int i = 1; i < n; ++i)
    {
        if (maxData < data[i])
            maxData = data[i];
    }
    int d = 1;//最大数的位数
    int p = 10;
    while (maxData >= p)
    {
        //p *= 10; 会有溢出的风险，所以采用降低maxData的数位
        maxData /= 10;
        ++d;
    }
    return d;
}
void radixsort(int data[], int n) //基数排序
{
    int d = maxbit(data, n);
    int *tmp = new int[n];
    int *count = new int[10]; //计数器
    int i, j, k;
    int radix = 1;
    for(i = 1; i <= d; i++) //进行d次排序
    {
        for(j = 0; j < 10; j++)
            count[j] = 0; //每次分配前清空计数器
        for(j = 0; j < n; j++)
        {
            k = (data[j] / radix) % 10; //统计每个桶中的记录数
            count[k]++;
        }
        for(j = 1; j < 10; j++)
            count[j] = count[j - 1] + count[j]; //将tmp中的位置依次分配给每个桶
        for(j = n - 1; j >= 0; j--) //将所有桶中记录依次收集到tmp中
        {
            k = (data[j] / radix) % 10;
            tmp[count[k] - 1] = data[j];
            count[k]--;
        }
        for(j = 0; j < n; j++) //将临时数组的内容复制到data中
            data[j] = tmp[j];
        radix = radix * 10;
    }
    delete []tmp;
    delete []count;
}