By

文章目錄
  1. 1. 排序算法概念
  2. 2. 排序算法
    1. 2.1. 冒泡排序(Sort Algorithm)
    2. 2.2. 堆排序(Heap Sort)
    3. 2.3. 快速排序(Quick Sort)
    4. 2.4. 归并排序(Merge Sort)
    5. 2.5. 插入排序(Insert Sort)
  3. 3. 总结

排序算法概念

  1. 时间复杂度 — 指执行算法所需要的计算工作量

    1. 平均时间复杂度 — 理论上一般情况的时间复杂度
    2. 最坏时间复杂度 — 特殊情况下（导致时间耗费最多的数据输入）
    3. 最优时间复杂度 — 特殊情况下（导致时间耗费最少的数据输入）

  2. 空间复杂度 — 指执行算法所需要的内存空间

排序算法

冒泡排序(Sort Algorithm)

基本思想：

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

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void bubbleSort(int* sortarray)
{
    //双重循环都跟数据大小有关
    //所以冒泡排序平均时间复杂度是O(square(n))
    for(int i = 0; i < intArraySize(sortarray); i++)
    {
        for(int j = i + 1; j < intArraySize(sortarray); j++)
        {
            if( sortarray[i] > sortarray[j] )
            {
                swap_time++;
                swap(sortarray[i], sortarray[j]);
            }
        }
    }
}

冒泡排序时间复杂度
平均时间复杂度：O(square(n))
最坏时间复杂度：O(square(n)) （每一次比较都需要交换）
最优时间复杂度：O(n) （第一次循环就完成所有排序而无需进行后面的，需要判断结束条件）

堆排序(Heap Sort)

相关概念

  1. 完全二叉树
    除最后一层外，每一层的节点数均达到最大值；在最后一层上只缺右边的若干结点
  2. 堆
    ki<=k(2i）且ki<=k(2i+1)(1≤i≤ n/2），当然，这是小根堆，大根堆则换成>=号。//k(i）相当于二叉树的非叶子结点，K(2i）则是左子节点，k(2i+1）是右子节点

基本思想
利用最大堆最小堆的特性，我们可以很容易的拿到最大或最小值，通过构建最大最小堆我们可以得到排序后的值

  1. 最大堆调整（Max_Heapify）：将堆的末端子节点作调整，使得子节点永远小于父节点
  2. 创建最大堆（Build_Max_Heap）：将堆所有数据重新排序
  3. 堆排序（HeapSort）：移除位在第一个数据的根节点，并做最大堆调整的递归运算

Code

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
63
64
65
//调整堆确保堆是最大堆，这里花O(log(n))，跟堆的深度有关
void heapAdjust(int* sortarray, int parentindex, int length)
{
	int max_index = parentindex;
	int left_child_index = parentindex * 2 + 1;
	int right_child_index = parentindex * 2 + 2;

	//Chose biggest one between parent and left&right child
	if( left_child_index < length && sortarray[left_child_index] > sortarray[max_index] )
	{
		max_index = left_child_index;
	}

	if( right_child_index < length && sortarray[right_child_index] > sortarray[max_index] )
	{
		max_index = right_child_index;
	}

	//If any child is bigger than parent, 
	//then we swap it and do adjust for child again to make sure meet max heap definition
	if( max_index != parentindex )
	{
		swap_time++;
		swap(sortarray[max_index], sortarray[parentindex]);
		heapAdjust(sortarray, max_index, length);
	}
}

//通过初试数据构建最大堆
void buildingHeap(int* sortarray)
{
	for( int i = int(intArraySize(sortarray)/2) - 1; i >= 0; i--)
	{
		//1.2 Adjust heap
		//Make sure meet max heap definition
		//Max Heap definition:
		// (k(i) >= k(2i) && k(i) >= k(2i+1))   (1 <= i <= n/2)
		heapAdjust(sortarray, i, intArraySize(sortarray));
	}
}

void heapSort(int* sortarray)
{
	//Steps:
	// 1. Build heap
	// 1.1 Init heap
	// 1.2 Adjust heap
	// 2. Sort heap

	//1. Build max heap
	// 1.1 Init heap
	//Assume we construct max heap
	buildingHeap(sortarray);
	//2. Sort heap
	//这里花O(n)，跟数据数量有关
	for( int i = intArraySize(sortarray) - 1; i > 0; i-- )
	{
		//swap first element and last element
		//do adjust heap process again to make sure the new array are still max heap
		swap(sortarray[i],sortarray[0]);
		//Due to we already building max heap before,
		//so  we just need to adjust for index 0 after we swap first and last element
		heapAdjust(sortarray, 0, i);
	}
}

堆排序时间复杂度
平均时间复杂度：O(n log(n))
最坏时间复杂度：O(n log(n))
最优时间复杂度：O(n log(n)) (时间复杂度都跟堆的深度和数据长度相关，无可避免的需要去做堆调整和堆排序
所以最坏时间复杂度和最优时间复杂度都是O(nlog(n)

快速排序(Quick Sort)

基本思想

  1. 选择一个值作为基准后，通过比较把小于基准值的值放到基准值左边，大于基准值的放到基准值右边，这样一来就有一个数据放在了正确位置。
  2. 通过分治的思想，将数据组不断细分成小数据组进行基准值的排序直到细分到只剩一个数据为止

Code

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
int partition(int* sortarray, int l, int r)
{
	//choose pivot
	int pivot = sortarray[r];
	int i = l;
	for( int j = l; j < r; j++ )
	{
		time_complexity++;
		if( sortarray[j] <= pivot )
		{
			swap(sortarray[i],sortarray[j]);
			i++;
		}
	}
	swap(sortarray[i], sortarray[r]);
	return i;
}

void quicksort(int* sortarray, int low, int high, bool benableoptimize)
{
	//partition
	//Here we use last element of array as pivot
	//recursion
	//Pivot chosen to optimize quicksort
	// median-of-three
	int pivotpos; 
	int middlepos = (high + 1) / 2;
	if( benableoptimize )
	{
		if( sortarray[low] > sortarray[middlepos] )
		{
			swap(sortarray[low],sortarray[middlepos]);
		}

		if( sortarray[middlepos] > sortarray[high] )
		{
			swap(sortarray[middlepos],sortarray[high]);
		}

		if( sortarray[low] > sortarray[middlepos] )
		{
			swap(sortarray[low], sortarray[middlepos]);
		}

		pivotpos = middlepos;
	}
	else
	{
		pivotpos = high;
	}
	 
	pivotpos=partition(sortarray,low,pivotpos);
	quicksort(sortarray,low,pivotpos-1,benableoptimize);
	quicksort(sortarray,pivotpos+1,high,benableoptimize);  
}

时间复杂度
平均时间复杂度：O(n log(n)) (细分的时候每一次都对半分)
最坏时间复杂度：O(n square(n)) （细分的时候每一次都分成一个和其他所有,所以在比较有序数据组面前快排效率不高）

最优时间复杂度：
快速排序可以通过选择更有效的基准值来提高效率
基准值会影响数据组的细分也就是影响后半部分分治的效率，所以最优时间复杂度取决于如何取基准值（上面提到median-of-three方式选基准值就是通过把第一和中间和最后元素排序后选取中间元素作为基准值来确保在细分的时候尽可能满足对半分从而提高效率）

归并排序(Merge Sort)

基本思想

  1. 通过分治思想，把数据组的排列细分成排序多个的小数据组后合并
  2. 通过比较两两有序的小数据组完成合并后的数据排序，然后和其他有序数据组再次进行比较合并，最终完成所有数据的排列和合并

Code

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
63
void merge(vector& sortarray, int start, int middle, int end)
{
	int left_size = middle - start + 1;
	int right_size = end - middle;
	vector left;
	vector right;
	for( int i = 0; i < left_size; i++ )
	{
		left.push_back(sortarray[start + i]);
	}

	for( int j = 0; j < right_size; j++ )
	{
		right.push_back(sortarray[j + middle + 1]);
	}

	int k = 0;
	int l = 0;
	int index = start;
	//The worst condition is compare n * log(n) - n + 1
	//The best condition is compare n * log(n) / 2
	while( k < left_size && l < right_size )
	{
		if( left[k] < right[l] )
		{
			sortarray[index] = left[k];
			k++;
		}
		else
		{
			sortarray[index] = right[l];
			l++;
		}
		index++;
	}

	while( k < left_size )
	{
		sortarray[index] = left[k];
		k++;
		index++;
	}

	while( l < right_size )
	{
		sortarray[index] = right[l];
		l++;
		index++;
	}
}

void mergesort(vector& sortarray, int start, int end)
{
	//sort first (subdivide array)
	//then merge (finally merge to together recursively)
	if( start < end )
	{
		int middle = (end + start) / 2;
		mergesort(sortarray, start, middle);
		mergesort(sortarray, middle + 1, end);
		merge(sortarray, start, middle, end);
	}
}

时间复杂度
平均时间复杂度：O( n log(n) )
最优时间复杂度：O( n )（数据组已经有序，只需要把细分数据合并）
最坏时间复杂度：O( n log(n) )

Note
因为归并排序需要存储细分后的数据组，所以归并排序比较占内存
归并比较次数 n介于 n log(n) - n + 1 和 n log(n) / 2
归并赋值次数2n log(n)
归并平均时间复杂度和最坏时间复杂度都是n log(n)
相比快速排序归并排序更稳定(最坏情况下)，而且更适合局部数据有序的情况

插入排序(Insert Sort)

基本思想
通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入

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

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void insertSort(int* sortarray)
{
	int i,j;
	int temp;
	//从第二个数开始取，依次插入，O(n)
	for( i = 1; i < intArraySize(sortarray); i++ )
	{
		temp = sortarray[i];
		//依次跟之前已经排序好的数组元素比较O(n)
		for( j = i - 1; j >= 0 && sortarray[j] > temp; j-- )
		{
			sortarray[j+1] = sortarray[j];
		}
		sortarray[j+1] = temp;
	}
}

时间复杂度
平均时间复杂度：O(square(n))
最坏时间复杂度：O(square(n))
最优时间复杂度：O(n)（数据已经是有序的情况下，不需要比较，直接插入）

总结

各排序算法有各自的优势，适合不同的情况。
相对稳定且时间复杂度低的排序算法：
堆排序，快速排序，归并排序

而归并排序相比快速排序更稳定（最坏情况下），更适合局部数据有序的情况，但归并的内存占用比较多

插入排序虽然时间复杂度比较高，但在已经排好序的数据面前，时间复杂度是O(n)
插入排序适合有序数据组且经常需要插入数据的情况

各排序算法时间复杂度总结：
来源：Visualizing Algorithms
Sort-Algorithem

参考：
8大排序算法图文讲解

推荐网站：
Visualizing Algorithms

文章目錄
  1. 1. 排序算法概念
  2. 2. 排序算法
    1. 2.1. 冒泡排序(Sort Algorithm)
    2. 2.2. 堆排序(Heap Sort)
    3. 2.3. 快速排序(Quick Sort)
    4. 2.4. 归并排序(Merge Sort)
    5. 2.5. 插入排序(Insert Sort)
  3. 3. 总结