算法

排序算法是程序设计最常用的算法 。排序算法有很多中,目的是按照某些标准对一堆数据进行排序,本文将介绍以下几种常见的排序算法。

sorting algorithm stability average time complexity spatial complexity
bubble sort $O(n^2)$ $O(1)$
selection sort × $O(n^2)$ $O(1) $
insertion sort $O(n^2) $ $O(1)$
shell sort × $O(n^{1.5})$ $O(1)$
quick sort × $O(n \cdot \log n)$ $O(\log n)$
merge sort $O(n \cdot \log n)$ $O(n) $
heap sort × $O(n \cdot \log n) $ $O(1)$
radix sort $O(d \cdot (n+r))$ $O(n+r)$
counting sort $O(n+r) $ $O(r)$
bucket sort $O(n + r)$ $O(n + r) $

其中 d 是整数的位数(100 是 3 位),r 是桶的个数。

下面为了简单阐述,我们总是对 n 个整数进行从大到小的排序。都是以 C++ 语言的方式讲解,如果想拓展到任意类型,利用 C++ 的模板实现即可。

1. 冒泡排序(bubble sort)

思想:把小的元素逐个往前调或者把大的元素逐个往后调,进行 n 轮。

template<typename T>
void bubble_sort(T arr[], int len) {
    T temp;
    for (unsigned i = 0; i < len - 1; i++)   // 需要进行 n 轮
        for (unsigned j = 0; j < len - 1 - i; j++) // 对剩下的元素进行扫描
	        if (arr[j] > arr[j + 1]) {      // 交换顺序
	            temp = arr[j];
	            arr[j] = arr[j + 1];
	            arr[j + 1] = temp;
	        }
}

在比较过程中,两个大小相等的元素不会交换前后顺序,所以冒泡排序是稳定的。最坏的情况是数组是倒序的,这时候每个步骤都需要交换数据。

2. 选择排序(selection sort)

思想:从剩余的元素中调出最大的元素放到末尾,进行 n 轮。

template<typename T>
void selection_sort(T arr[], int len) {
    T temp;
    for (unsigned i = 0; i < len - 1; i++) { // n 轮循环 
        unsigned k = i;
    	for(unsigned j = i+1; j < len; j++) {  // 将最小的下标记录在 k 上 
    		if(arr[k] > arr[j])
    			k = j;
		}
		if(k != i){          // 将最小的放到前面 
			temp = arr[i];
			arr[i] = arr[k];
			arr[k] = temp;
		}
	}
}

交换步骤可能导致两个大小相等的元素发生顺序变化,所以是不稳定的,例如序列

3 3 1

交换的次数没有冒泡排序那么频繁,但是改变不了它的时间复杂度。

3. 插入排序(insertion sort)

思想:将一个数据插入到已经排好序的数组中。

template<typename T>
void insertion_sort(T arr[], int len) {
    T temp;
    for (int i = 1; i < len; i++) { // 默认第一个为有序数组,剩下的一个一个插入到前面去 
    	temp = arr[i];
		int j = i-1;
		//与已排序的数逐一比较,大于temp时,该数移后
		while(( j >= 0 ) && (arr[j] > temp)){
			arr[j+1]=arr[j];
			j--;
		}  
		arr[j+1] = temp;  // 将其 temp 插入到合适的位置 
	}
}

注意:由于 j 可能小于 0 ,所以这里我的循环变量都是用 int 型。

4. 希尔排序(shell 排序)

思想:插入排序的改进版本,希尔排序是把记录按下标的一定增量分组,对每组使用直接插入排序算法排序;随着增量逐渐减少,每组包含的记录越来越多,当增量减至1时,整个文件恰被分成一组,算法便终止。

template<typename T>
void insertion_sort(T arr[], int len, int step) {
    T temp;
    for (int i = step; i < len; i += step) { // 步长为 step 的插入排序 
    	temp = arr[i];
		int j = i-step;
		// 与已排序的数逐一比较,大于 temp 时,该数向后移动 step 个单位 
		while(( j >= 0 ) && (arr[j] > temp)){
			arr[j+step]=arr[j];
			j -= step;
		}  
		arr[j+step] = temp;  // 将其 temp 插入到合适的位置 
	}
}

template<typename T>
void shell_sort(T arr[], int len){
	for(int step = len/2; step; step /= 2){ // 初始步长定为 len/2 比较容易实现
		for(int i = 0; i < step; i++){
			insertion_sort(&arr[i], len - i, step);  // 对第 i 组进行插入排序 
		} 
	}
} 

当 step 退化到 1 的时候,其实就是插入排序了,而希尔算法优化了插入过程。分组时,不同小组的排序不一致导致算法不稳定。复杂度比起插入排序明显下降。

5. 快速排序

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

template<typename T>
void quick_sort(T arr[], int low, int high) {
    if (high <= low) return;  
   
    T flag = arr[low];
    int i = low + 1;
    int j = high;
    while(true){
		while (arr[i] < flag && i < high) i++;  // 从左到右找不小于 flag 的值
		while (arr[j] > flag && j > low)  j--;  // 从右到左找比 flag 小的值
		
		if(i >= j) break;   // 没找到直接跳出循环 
		
		// 将 arr[j] 挪到低处,arr[i] 挪到高处,这里互相交换即可 
		T temp = arr[i];
		arr[i] = arr[j];
		arr[j] = temp; 
	}
	// 将 arr[j] 挪到arr[low] 处,将中枢值 flag 放到 arr[j] 中 
	arr[low] = arr[j];
	arr[j] = flag; 
	
	// flag 左边的数据不大于 flag ,flag 右边的数据不小于 flag ,对这两部分进一步排序 
	quick_sort(arr, low, j-1);
	quick_sort(arr, j+1, high);  
}

快速排序是不稳定的,交换过程中最右的可能被调到左边,例如下例中的 3 的顺序会被打乱。

3 3 2 4 3

由于二分后排序导致规模变化特别快,这就是快排的复杂度这么低的原因。

6. 归并排序(merge sort)

思想:建立在归并操作上的一种有效的排序算法,该算法是采用分治法(Divide and Conquer)的一个非常典型的应用。

template<typename T>
void merge(T arr[], T temp[], int start_index, int mid_index, int end_index) {
	int i = start_index, j = mid_index, k = start_index;
	while(i < mid_index && j <= end_index){   // 谁小谁上 
		if(arr[i] > arr[j]) 
			temp[k++] = arr[j++];
		else
			temp[k++] = arr[i++];
	}
	while(i < mid_index)           // 处理剩余数据 
		temp[k++] = arr[i++];
	while(j <= end_index)
		temp[k++] = arr[j++];
	
	// 拷贝回原数组 
	for(i = start_index; i <= end_index; i ++)
        arr[i] = temp[i];
}

template<typename T>
void merge_sort(T arr[], T temp[], int start_index, int end_index) {
    if(start_index < end_index) {
    	int mid_index = start_index + (end_index - start_index) / 2;  //避免溢出
		merge_sort(arr, temp, start_index, mid_index);
		merge_sort(arr, temp, mid_index + 1, end_index); 
		merge(arr, temp, start_index, mid_index+1, end_index);  
	}
}

归并排序的递归形式比较直观,但是利用迭代方式也不难。归并排序还有个优点:具有稳定性。

7. 堆排序

思想:利用堆这种数据结构所设计的一种排序算法。堆是一个近似完全二叉树的结构,并同时满足堆积的性质:即子结点的键值或索引总是小于(或者大于)它的父节点。利用这个性质,我们实现以下步骤

  1. heapify :从最后一个父节点开始,进行调整,保证子节点的值小于父节点的值。
  2. build max heap :倒序遍历父节点的过程中对每个父节点进行 1 操作,构建最大堆。
  3. heap sort :每次 2 步骤构建出的树中,根元素一定是最大的,将其取出,剩下的元素重复 1 和 2 过程。
template<typename T>
void heapify(T arr[], int start, int end) {
	// 建立父节点指标和子节点指标
	int dad = start;
	int son = dad * 2 + 1;
	while (son <= end) { // 子节点指标在范围内才做比较
		if (son + 1 <= end && arr[son] < arr[son+1])  // 先比较两个子节点大小,选择最大的
			son ++;
		if(arr[dad] > arr[son])   // 如果父节点大于子节点代表调整完毕,直接跳出韩束
			return;
		else {  // 交换父子内容再继续子节点和孙节点比较 
			swap(arr[dad], arr[son]);
			dad = son;
			son = dad * 2 + 1;	
		} 
	} 
}
 
template<typename T>
void heap_sort(T arr[], int len) {
  	// 初始化,i 从最后一个父节点开始调整
	for(int i = len / 2 - 1; i >= 0; i--) 
		heapify(arr, i, len - 1);
	// 先将第一个元素和已经排好的元素前一位做交换,再从新调整(刚调整的元素之前的元素),直到排序完毕
	for (int i = len - 1; i > 0; i--) {
		swap(arr[0], arr[i]);
		heapify(arr, 0, i - 1);
	}
}

8. 基数排序

思想:将所有待比较数值(正整数)统一为同样的数位长度,数位较短的数前面补零。然后,从最低位开始,依次进行一次排序。这样从最低位排序一直到最高位排序完成以后, 数列就变成一个有序序列。

template<typename T>
int max_bit(T arr[], int len) {
	int d = 1;  // 保存最大位数
	int p = 10; 
	for(int i = 0; i < len; i++)   // 每个数都要判断 
		while(arr[i] >= p){
			p *= 10;
			d++;
		} 
	return d;
}
 
template<typename T>
void radix_sort(T arr[], int len) {
    int d = max_bit(arr, len);
    int *tmp = new int[len];
    int *count = new int[10];  // 计数器,0~9 
	int radix = 1;
	while(d --) {  // 进行 d 次 排序 
		for(int i = 0; i < 10; i ++)
			count[i] = 0;           // 每次分配前清空计数器
		for(int i = 0; i < len; i ++){
			int j = (arr[i] / radix) % 10; // 统计每个桶中的记录数 
			count[j]++;
		}
		for (int i = 1; i < 10; i ++)
			count[i] = count[i-1] + count[i]; // 将 tmp 中的位置依次分配给每个桶
		for (int i = len-1; i >= 0; i--) { // 将所有桶中记录依次收集到tmp中 
			int j = (arr[i] / radix) % 10;
			tmp[count[j]-1] = arr[i];
			count[j]--; 
		}
		for(int i = 0; i < len; i++)  // 将临时数组内容复制回 arr	 
		 	arr[i] = tmp[i];
		radix = radix * 10;
	} 
	delete[]tmp;
	delete[]count;
}

该算法要经过 d 轮,每轮里面首先对 n 个记录进行分配,然后对 k 个组合进行收集,因此时间复杂度为 $O(d \cdot (n+r))$ 。这种排序适合 d 比较小的时候,让我想到可以用在字典排序里面。

9. 计数排序

思想:使用一个额外的数组 buckets,其中第 i 个元素是待排序数组 arr 中值等于 i 的元素的个数。然后根据数组 buckets 来将 arr 中的元素排到正确的位置。它只能对整数进行排序。这是一个稳定的排序算法。

template<typename T>
void counting_sort(T arr[], int len) {
	T min = arr[0], max = arr[0];     // 1. 找出最大值和最小值
	for(int i = 1; i < len; i ++) {
		if (min > arr[i]) min = arr[i];
		if (max < arr[i]) max = arr[i];
	} 
	
	int buckets_len = max - min + 1; 
	T* buckets = new T[buckets_len];     // 2. 建立计数数组(桶)并置零 
	for (int i = 0; i < buckets_len; i ++) 
		buckets[i] = 0;
		
	for(int i = 0; i < len; i ++) {      // 3. 对每一个数继续计数归类 
		buckets[arr[i] - min] ++ ;
	}
	
	int j = 0;                          // 4. 排序,按顺序从桶里面取东西 
	for(int i = 0; i < buckets_len; i ++){
		while(buckets[i]) {
			buckets[i] --;
			arr[j++] = i + min;
		} 
	} 
	
    delete[]buckets;
}

10. 桶排序

思想:桶排序是计数排序的升级版。计数排序的映射很简单,而桶排序利用了函数的映射关系,高效与否的关键就在于这个映射函数的确定。

工作原理:假设输入数据服从均匀分布,将数据分到有限数量的桶里,每个桶再分别排序(有可能再使用别的排序算法或是以递归方式继续使用桶排序进行。数据偏差不宜过大。

桶排序没有一个通用的算法,具体问题具体分析,下面我们给出几个例子供大家感受。

1. 海量数据排序

2. 数据定位

总结

最后三个算法都用到了桶的概念,但是使用不同

数据集小的话一般使用快排或者归并排序,选择在于你是否需要稳定。

数据集大的话需要对数据进行分析后再选择。