7种常见排序算法

| 分类于

前言

排序在我们的编程之路上一直伴随着我们,从最初接触到的冒泡排序,再到选择排序,再到如今的归并排序,快速排序…排序在生活中也一直扮演着重要的角色,淘宝中的按价格,按人气升降序,其实都离不开基本的排序算法.本文便在这里着重讲解一下排序中的四大类((插入排序/选择排序/交换排序/归并排序))中的7种排序(直接插入排序,希尔排序,选择排序,堆排序,冒泡排序,快速排序,归并排序)~

插入排序

基本思想:每一步将一个待排序的元素,按其排序码的大小,插入到前面已经排好序的一组元素的合适位置上去,直到元素全部插完为止

直接插入排序

思路: 给定一个无序序列,我们假定将此序列分为两部分,前面一部分为有序序列,后面一部分为无序序列,那么我们只需要将无序序列中的数据按照一定插入算法(从小到大)插入到有序序列中即可.具体实现时,我们可认为当前半部序列中只有一个元素时,那么这个序列一定有序.及有序序列从只有数组第一个元素存在开始,我们依次从第二个元素开始与有序序列比较并插入

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
void InsertSort(int arr[], int size)
{
	int i, j;
	int key;     								//关键码,即每次要插入元素
	for (i = 1; i < size; i++)
	{
		key = arr[i];
		for (j = i - 1; j >= 0; j--)			//即将被插入元素从有序序列最后一个元素开始比较找到位置并插入
		{
			if (key >= arr[j])
			{
				break;
			}
			else
			{
			    //也可以直接写成交换的形式
				//int tmp = arr[j + 1];
				//arr[j + 1] = arr[j];
				//arr[j] = tmp;
				arr[j + 1] = arr[j];
			}
		}
		arr[j + 1] = key;
	}
}


复杂度分析:
时间复杂度: 最好情况(完全有序,则只需扫描一次)/平均/最差情况(完全逆序) O(n)/O(n^2)/O(n^2)
空间复杂度: 此算法没有调用其它多余的空间,所以空间复杂度为O(1)
稳定性:
元素集合越接近有序,直接插入排序算法效率越高,并且这是一种稳定的排序算法,因为我们可以人为控制相同大小元素的插入方式及位置

希尔排序

希尔排序又称缩小增量排序,是插入排序的一种高速而稳定的改进版本;
我们在进行直接插入排序时注意到,如果序列越接近有序,那么插入的效率就会越高.所以有个名叫希尔的大佬便提出了此排序算法,他主要分为两步:
1.先将整个待排元素序列分割成若干个子序列(由相隔某个”增量”的元素组成的)分别进行直接插入排序;
2.然后依次缩减增量再次进行排序,待整个序列中的元素基本有序(增量足够小)时,再对全体元素进行一次直接插入排序.
总言之,先分组,对每一组进行插排,然后对整个数列进行插排

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
#if 1
void __InsertSort(int arr[], int size, int gap)
{
	for (int g = 0; g < gap; g++) 					//分别排序多组元素
	{
		int key;
		int i, j;
		for (i = gap + g; i < size; i += gap)        //此处要注意间隔问题
		{
			key = arr[i];
			for (j = i - gap; j >= 0; j-=gap)
			{
				if (key >= arr[j])
				{
					break;
				}
				else
				{
					arr[j + gap] = arr[j];
				}
			}
			arr[j + gap] = key;
		}
	}
}
#else
void __InsertSort(int arr[], int size, int gap)
{
	int i, j;
	int key;
	for (i = gap; i < size; i ++)
	{
		key = arr[i];
		for (j = i - gap; j >= 0; j -= gap)
		{
			if (key >= arr[j])
			{
				break;
			}
			else
			{
				arr[j + gap] = arr[j];
			}
		}
		arr[j + gap] = key;
	}
}
#endif

void ShellSort(int array[], int size)
{
	int gap = size;
	// gap 动态变化
	while (1) {
		gap = gap / 3 + 1;          		//按照指定的算法计算每次分组时的间隔
		__InsertSort(array, size, gap);
		if (gap == 1) {      				//当间隔为1时,及证明已经排序完成
			break;
		}
	}
}

复杂度分析:
时间复杂度: 最好/平均/最差 O(n)/O(n^1.2~1.3)/O(n^2)
空间复杂度: O(1)
稳定性:希尔排序由于要划分组别,并且划分元素在哪个组别都是不确定的,所以希尔排序是一种不稳定的排序算法

选择排序

基本思想:每一趟(第i躺,i=0,1,…,n-2)在后面n-i个待排序的数据元素集合中选出关键码最小的数据元素,作为有序元素序列的第i个元素.待到第n-2趟做完,待排序元素集合中只剩下一个元素,排序结束

直接选择排序

基本思路:在一个无序序列中构建出一个有序序列.遍历序列,每次都取出最小的元素依次放在序列前半部,直至后半部无序序列越来越小,便排完了整个序列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
void SelectSort(int arr[], int size)
{
	int i,j,k;
	for(i=0; i<size; i++)
	{
		k = i;
		for(j=i+1; j<size; j++)
		{
			if(arr[j]>= arr[k])
			{
				break;
			}
			else
			{
				k = j;
			}
		}
		
		if(k != i)
		{
			Swap(arr+k,arr+i);
		}
	}
}

复杂度分析:
时间复杂度: 最好/平均/最差 O(n)/O(n^2)/O(n^2)
空间复杂度: O(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
25
26
27
28
	void SelectSortOP(int arr[], int size)
{
	int left = 0;
	int right = size - 1;
	while (left < right)
	{
		int max = left;
		int min = left;
		for (int i = left+1; i <= right; i++)
		{
			if (arr[i] > arr[max])
			{
				max = i;
			}
			if (arr[i] < arr[min])
			{
				min = i;
			}
		}
		Swap(arr + left, arr + min);
		if (max == left)
		{
			max = min;
		}
		Swap(arr + right, arr + max);
		left++; right--;	  
	}
}

堆排序

堆具有其特殊的性质,在一个堆中,我们总能很容易的找到一个或大(大堆第一个元素)或小(小堆第一个元素)的最值.利用这个性质我们可以改变一个序列内部的存储顺序,从而实现排序
堆排序基本思想:
1.在一个已经创建好的堆中(这里我们使用的大顶堆),把堆顶arr[0]元素和当前堆的最后一个元素交换;
2.堆元素个数减1(即在逻辑上抹除交换后的最后一个元素,使他不参与下一次的调整)
3.再次进行向下调整,重复步骤1,2;
直到调整到堆中只有一个元素,自己跟自己交换后,整个堆就已经被排序成为一个从小到大的有序序列了

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
//向下调整
void AdjustDown(int arr[], int size, int root)
{
	while (1)
	{
		int left = root * 2 + 1;
		int right = root * 2 + 2;

		int max = left;
		if (left >= size)
		{
			return;
		}

		if (right<size && arr[right]>arr[left])
		{
			max = right;
		}

		if (arr[root] < arr[max])
		{
			Swap(arr + root, arr + max);		
		}
		else
		{
			return;
		}	
		root = max;
	}
}

void CreatHeap(int arr[], int size)
{
	for (int i = (size - 2) / 2; i >= 0; i--)
	{
		AdjustDown(arr, size, i);                 //创建堆的过程其实就是对每一个非叶子节点的向下调整过程
	}
}

void HeapSort(int arr[], int size)
{
	CreatHeap(arr, size);                     //先创建堆

	for (int i = 0; i < size; i++)
	{
		Swap(&arr[0], &arr[size - 1 - i]);     //每次将堆中最大元素放到堆末尾,并将size-1,即下次调整不再对末尾数据做处理
		AdjustDown(arr, size-1-i, 0);			//向下调整
	}
}

复杂度分析:
时间复杂度: 把一颗完全二叉树调整为堆,以及每次将堆顶元素交换后进行调整的时间复杂度均为O(logn),所以堆排序的时间复杂度为O(nlogn)
空间复杂度: O(1)
稳定性: 堆排序是一种不稳定的排序算法

交换排序

利用交换元素的位置进行排序的方法称为交换排序
常用的交换排序的方法: 冒泡排序和快速排序

冒泡排序

这是一种很基础的排序算法,其思路就是挨个比较两个元素,将大的元素放到序列尾部

1
2
3
4
5
6
7
8
9
10
11
12
13
14
void BubbleSort(int arr[], int size)
{
	int i,j;
	for(i=0; i<size; i++)
	{
		for(j=0; j<size-1-i; j++)
		{
			if(arr[j+1] < arr[j])
			{
				Swap(arr+j+1,arr+j);
			}
		}
	}
}

快速排序

快速排序是Hoare在1962年提出的一种二叉树结构的交换排序方法,其基本思想为:任取待排序元素序列中的某元素作为基准值,按照该排序码将待排序集合分割成两个子列,左子序列中的元素均小于基准值,右子序列中所有元素均大于基准值,然后左右序列重复该过程,知道所有元素都排列在相应位置上为止
直接上代码解释:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
//快速排序
void __QuickSort(int arr[], int left, int right)
{
	if (left == right)
	{
		return;
	}
	if (left > right)
	{
		return;
	}

	//按照基准值将left和right标记区间划分为两部分
	int div = Patition_1(arr, left, right);
	//排列左边部分
	__QuickSort(arr, left, div - 1);
	//排列右边部分
	__QuickSort(arr, div+1, right);
}

void QuickSort(int arr[], int size)
{
	__QuickSort(arr, 0, size-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
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
```c 

//hover法/左右指针法
//原理:定义两个指针begin和end,一开始时使begin位于left,end位于right,两头同时开始遍历整个数列,
//从begin开始,如果他小于等于基准值,就往后一个位置,如果end大于等于基准值,就往前一个位置,然后交换begin和end
//直到不满足循环的条件跳出后交换right和begin,此时便排好了一次序列,begin左边的小于begin,右边的大于begin
int Patition_1(int arr[], int left, int right)
{
	int begin = left;
	int end = right;

	while (begin < end)
	{
		while (begin < end && arr[begin] <= arr[right])
		{
			begin++;
		}
		while (begin < end && arr[end] >= arr[right])
		{
			end--;
		}
		Swap(arr + begin, arr + end);
	}
	Swap(arr + begin, arr + right);
	return begin;
}

//指针遍历法
//原理:定义两个指针cur和div,用div来记录最终的基准值,一开始的基准值仍然是最右边的那个.
//让cur从left开始向后遍历,只要发现比基准值(arr[right])小的数便交换cur和div的值,并使div+1.直到cur遍历到right,说明在此时从div开始
//到cur-1都是比这个基准值大的数字,所以交换此时的div和right上的值,便完成了一次排序,在div左边的值都小于div,在div右边的值都大于div
int Patition_3(int arr[], int left, int right)  
{
	int cur = left;
	int div = left;

	for (cur = left; cur < right; cur++)
	{
		if (arr[cur] < arr[right])
		{
			Swap(arr + cur, arr + div);
			div++;
		}	
	}
	Swap(arr + div, arr + right);
	return div;
}

复杂度分析:
时间复杂度: 最好/最差/平均 O(N*logN)/O(n^2)/O(n^2)
空间复杂度: 最好/最差/平均 O(logN)/O(N)/O(N)
稳定性: 不稳定
如上便是快速排序~

归并排序