likes
comments
collection
share

经典排序算法的实现及解析

作者站长头像
站长
· 阅读数 29

经典排序算法的实现及解析

作者：光火

邮箱：victor_b_zhang@163.com

  • 尽管在工程实践中，很多程序员习惯用一手 sort 打天下，但是掌握基本的排序算法还是颇为必要的。这在于，经典排序算法的实现思路往往简单朴素，却又具备良好的启发性和拓展性，非常利于我们理解算法的本质及精妙之处。而且，从功利的角度出发，很多企业时常会要求面试者书写排序算法或解决排序相关的问题。这时，充分领悟经典排序算法的内核就变得更为重要了。
  • 因此，话不多说，让我们直接进入正题！需要特别指出的是，为了便于初学者理解，本文在表述过程中可能会存在诸多不严谨的地方，而且给出的代码也并非是该排序算法的最优实现策略，还望各位读者适当理解，各倾陆海。
排序算法平均时间复杂度空间复杂度稳定性基本原理
冒泡排序O(n2)\Omicron(n^2)O(n2)O(1)\Omicron(1)O(1)稳定两两比较，不断交换逆序对
选择排序O(n2)\Omicron(n^2)O(n2)O(1)\Omicron(1)O(1)不稳定将区间最值放置在对应的位置上
插入排序O(n2)\Omicron(n^2)O(n2)O(1)\Omicron(1)O(1)稳定在已排序区间中自右向左插入元素
希尔排序O(nlog⁡n)\Omicron(n\log n)O(nlogn)O(1)\Omicron(1)O(1)不稳定改进插入排序，划分尺度由粗到细
归并排序O(nlog⁡n)\Omicron(n\log n)O(nlogn)O(n)\Omicron(n)O(n)稳定二分数组，各自排序，统一合并
快速排序O(nlog⁡n)\Omicron(n\log n)O(nlogn)O(1)\Omicron(1)O(1)不稳定以基准元素为分割点划分数组
基数排序O(n⋅k)\Omicron(n\cdot k)O(n⋅k)O(n+k)\Omicron(n + k)O(n+k)稳定从最低位出发，施行多趟桶排序
堆排序O(nlog⁡n)\Omicron(n\log n)O(nlogn)O(1)\Omicron(1)O(1)不稳定构建堆，进行置换-下滤调整

冒泡排序

思路：对于一个已排序数组，它不应存在逆序对。因此，我们可以两两比较待排元素，倘若它们逆序，就交换二者的位置，直至数组完全有序。

// function call : [l , r)
void bubbleSort(int* arr, int l, int r) {
	if(arr == nullptr || r - l < 2)
		return;
		
	bool swapped = true;
	int swapped_index = -1;
	int unsorted_index = r - 1;
	
	while(swapped) {
		swapped = false;
		for(int i = l; i < unsorted_index; i ++) {
			if(arr[i] > arr[i + 1]) {
				swapped = true;
				swapped_index = i;
				swap(arr[i], arr[i + 1]);
			}
		}
		unsorted_index = swapped_index;
	} 
}
  • swapped 用于标记数组中是否进行过元素交换，倘若 swapped = false，则证明数组中已经不存在逆序对，故跳出循环；
  • swapped_index 表示上次发生交换的位置，unsorted_index 则代表最后一个未经排序的位置；
  • 由于冒泡排序每轮都会将当前未排序的最大元素挪动到数组右端的对应位置上，因此我们可以不断更新 for 循环的上界，也可以理解为 [unsorted_index, r) 这一区间内的元素已经摆放好了；

选择排序

思路：选择排序的思路最为直截了当，每次将待排元素的最值放置在对应位置上，直至数组完全有序。下面给出这一思路的基本实现，该代码还可进一步地优化，感兴趣的读者不妨尝试一下。

// function call : [l , r)
void selectSort(int* arr, int l, int r) {
	if(arr == nullptr || r - l < 2)
		return;

	for(int i = l; i < r; i ++) {
		int min_pos = i;
		for(int j = i + 1; j < r; j ++)
			if(arr[j] < arr[min_pos])
				min_pos = j;
		swap(arr[i], arr[min_pos]);
	}
}
  • min_pos 用于记录当前未排序元素的最小元对应的索引，它应当放置在位置 i 上，因此当内层 for 循环结束后，我们交换 arr[i] 和 arr[min_pos]。

插入排序

思路：对于一个包含 n(n≥2)n (n\geq 2)n(n≥2) 个元素的待排序数组，我们总是假设它的前 n−1n - 1n−1 个元素已经排好顺序，现将第 nnn 个元素插入到前面已然有序的序列之中，并使得整个区间仍旧保持有序。

// function call : [l , r)
void insertSort(int* arr, int l, int r) {
	if(arr == nullptr || r - l < 2)
		return;

	for(int i = l + 1; i < r; i ++) {
		int tot = arr[i], pos = i - 1;
		while(pos >= l && arr[pos] > tot) {
			arr[pos + 1] = arr[pos];
			pos --;
		}
		arr[pos + 1] = tot;
	}
}
  • 初始状态下，我们总是可以将数组最左侧的元素 arr[l] 作为一个区间，由于该区间只包含一个元素，因此它必然是有序的。接下来，我们将从第二个元素开始审视。所以，外层 for 循环 i 的初值为 l + 1；
  • 我们以 tot 标记待排元素，用 pos 作为左侧已排序区间的指针。在确保不越界的前提下，内层的 while 循环每次将 tot 与 arr[pos] 进行比较，倘若 arr[pos] > tot，则说明待排元素应当放置在 arr[pos] 的左边。因此，我们将当前的 arr[pos] 向右挪动一个位置，并让 pos --，即将指针左移，继续为 tot 寻觅位置。当然，pos 并非严格意义上的指针，只是一个标记；
  • 当 while 循环的条件不再满足时，pos + 1 即为 tot 应当处在的位置。这非常容易理解，考虑特殊情况，倘若 tot 比左侧区间的最大元素 arr[i - 1] 还大，那么说明 tot 就应该放在位置 i 上，而 pos 的初值刚好为 i - 1，因此有 arr[pos + 1] = tot；

希尔排序

思路：希尔排序又称缩小增量排序，是一种基于插入排序的改进策略。它首先会选取一个整数作为间隔，将全体元素划分为若干大组，再分别进行插入排序。随后间隔被逐步缩小，直至为 1，即将全体元素放在同一组中排序，但由于此前粗尺度上的排序已经大幅度减少了逆序对的数目，因此效率仍旧很高。

// function call : [l , r)
void shellSort(int* arr, int l, int r) {
	if(arr == nullptr || r - l < 2) 
		return;
		
	int count = r - l, tot = 0;
	for (int step = count / 2; step > 0; step /= 2)
		for (int i = l + step; i < r; i ++) {
			tot = arr[i];
			int j = i - step;
			while (j >= l && arr[j] > tot) {
				arr[j + step] = arr[j];
				j -= step;
			}
			arr[j + step] = tot;
		}
}
  • 代码中的 step 即为间隔，外层 for 循环首先将其置为 count / 2，之后每次都将其变为原来的一半，即逐步缩小间隔，重新分组；
  • 位于同一大组中的元素一般是不相邻的，它们彼此间隔 step，因此在内层的 while 循环中，我们每次将 j 向前移动 step 个位置；

归并排序

思路：对于一个包含 n(n≥2)n(n≥2)n(n≥2) 个元素的待排序数组，我们将其从中间切开，形成两个互不重叠的部分，并分别对它们进行排序。如此，我们将得到两个有序的子区间，然后再对它们进行合并，即可拼接出原数组。归并排序的大致实现过程可以分为两步，一是划分，二是合并。排序实则是由合并过程中完成的。二分操作会持续到子区间只包含一个元素，此时该区间显然有序，因此我们可以将其与另外的子区间进行合并。

// function call : [l , r)
void mergeSort(int* arr, int* tmp, int l, int r) {
	if (r - l < 2 || arr == nullptr)
		return;

	int m = (l + r) / 2;
	mergeSort(arr, tmp, l, m);
	mergeSort(arr, tmp, m, r);

	int i = l, j = m, k = l;
	while (i < m && j < r) {
		if (arr[i] < arr[j])
			tmp[k ++] = arr[i ++];
		else tmp[k ++] = arr[j ++];
	}
	while (j < r) tmp[k ++] = arr[j ++];
	while (i < m) tmp[k ++] = arr[i ++];

	for (int v = l; v < r; v++)
		arr[v] = tmp[v];
}
  • 归并排序需要 O(n)\Omicron(n)O(n) 的额外空间，即代码中的 tmp。每次 mergeSort，我们都要将 tmp 赋值到 arr 之中，从而保证原数组的对应部分也是有序的，这是我们处理更大规模区间的基础，即该区间的两个子部分应当分别有序，如此方能快速地进行合并；
  • 合并的过程主要是三个 while 循环在发挥作用，其中后两个 while 循环主要用于将子区间剩余的元素搬到 tmp 中去。这在于，第一个 while 循环的结束条件是 i >= m || j >= r，即至少有一个子区间已经全部放置在了 tmp 之中。这时，我们还要将另一个子区间剩余的部分也按照顺序加进 tmp。不过幸运的是，余下的这些元素天然有序，因此直接安放即可；

快速排序

闲话：

  • 快速排序被广泛认为是目前最好的一种内部排序方式。甚至在很多人看来，掌握快速排序就基本等同于掌握了排序算法。利用 xxxxxxxxx 实现个快排吧，也是应届生求职时经常遇到的面试题。
  • 那么，平均时间复杂度为 O(nlog⁡n)\Omicron(n\log n)O(nlogn) ，最坏情形下可达 O(n2)\Omicron(n^2)O(n2) 的快速排序为何如此受人青睐呢？这还是要归功于它的实际效果，如果说 KMPKMPKMP 算法只具备理论价值，那么快速排序则同时拥有理论和应用价值。《算法导论》一书中针对快速排序有着专门的论述和配套的习题，建议读者根据个人需求去阅读一番，想必会有所收获。总体而言，快速排序的性能十分优越，当数据量达到一定的规模时，它的执行速度会明显快于归并排序且不需要额外的内存空间。 思路：快速排序的大体流程可以看作是率先选择数组中的一个元素作为基准，然后将它放置在正确的位置上，并满足位于其左侧的元素全部 <= 它，而位于其右侧的全部 >= 它，尽管两侧未必是有序的。不断重复这个过程，直到整个数组全部有序。
// function call : [l , r]
void quickSort(int* arr, int l, int r) {
	if(l >= r || arr == nullptr) 
		return;
	
	int i = l, j = r;
	int divider = arr[l];
	
	while(i < j) {
		while(arr[j] >= divider && i < j) j --;
		while(arr[i] <= divider && i < j) i ++;
		if(i < j) swap(arr[i], arr[j]);
	}
	
	arr[l] = arr[i];
	arr[i] = divider;
	quickSort(arr, l, i - 1);
	quickSort(arr, i + 1, r);
}
  • 需要特别注意，上述实现中 r 作为数组的右端点，也包含在闭区间中；
  • 我们选取了数组中最左侧的元素 arr[l] 作为基准元，一种更能应对特定输入的方法是随机选取数组的一个元素，然后交换它与 arr[l] 的位置，再进行排序；
  • i 和 j 相当于两个“指针”，分别位于区间的两端，通过移动 i 和 j 的位置，即可将该区间的所有元素与 divider 进行比较；
  • 当跳出外层循环时，i 即为 divider 应当放置的位置，因此首先将 arr[i] 搬至 l 处，再将原来的 arr[l] 即 divider 放置在位置 i 上。由于此时 i 号位已经安置好了，因此后续的递归过程就无需再考虑 i 了；

基数排序

思路：基数排序是一种非比较型的整数排序算法。本文给出的实现只适用于排列正整数，但是通过一定的修改，就可以拓宽其使用范围。基数排序从最低位开始施行多趟桶排序，对于每一数位的排列均在上一数位的基础上进行，当针对最高位的扫描结束时，整个数组也就有序了。建议读者随机构造一组正整数输入，然后手动计算一遍，马上就可以领悟其原理。

// function call : [l , r)
void radixSort(int* arr, int l, int r) {
	if(arr == nullptr || r - l < 2)
		return;
		
	int max_val = arr[l], max_bit = 0;
	for (int i = l + 1; i < r; i ++)
		if (max_val < arr[i])
			max_val = arr[i];
	while (max_val > 0) max_val /= 10, max_bit ++;

	int radix = 1;
	int* cnt = new int[10];
	int* tmp = new int[r - l];
	for (int i = 1; i <= max_bit; i ++) {
		for (int j = 0; j < 10; j ++)
			cnt[j] = 0;
		for (int j = l; j < r; j ++)
			cnt[(arr[j] / radix) % 10] ++;
		for (int j = 1; j < 10; j ++)
			cnt[j] += cnt[j - 1];
		for (int j = r - 1; j >= l; j --) {
			int tot = (arr[j] / radix) % 10;
			tmp[cnt[tot] - 1] = arr[j];
			cnt[tot] --;
		}
		for (int j = l; j < r; j ++)
			arr[j] = tmp[j];
		radix = radix * 10;
	}
	delete[] cnt, tmp;
}
  • 在正式排序之前，我们需要找到数组中元素的最大值 max_val，用以确定最大位数 max_bit；
  • cnt 的下标范围为 0 ~ 9，正好对应了十进制下每位数字的可选值。我们依据 arr[j] 在 radix 位上的数字对 cnt 进行赋值，内层的第三个 for 循环，cnt[j] += cnt[j - 1] 则可以更为方便地定位相应的 arr[j]；
  • 类似于归并排序，我们需要一个临时数组 tmp，辅助我们将每趟排序后的结果返还给 arr；

堆排序

思路：堆是一种基于完全二叉树的数据结构，它一般被用于构建优先级队列。因此，相较于将全体元素进行排序，它更适用于去寻觅数据中前 KKK 个最大或最小的元素。不过出于全面性的考虑，下述还是给出了一种堆排序的实现方式。首先，根据堆合并法，由输入构造出一个大顶堆，随后再不断进行置换-下滤调整。

void heapify(int* arr, int begin, int end) {
	int parent = begin;
	int child = parent * 2 + 1;

	while(child <= end) {
		if(child + 1 <= end && arr[child] < arr[child + 1])
			child ++;
		if(arr[child] <= arr[parent])
			return;
		else {
			swap(arr[child], arr[parent]);

			parent = child;
			child = parent * 2 + 1;
		}
	}
}

// function call : [l , r)
void heapSort(int* arr, int l, int r) {
	if(arr == nullptr || r - l < 2)
		return;

	for(int i = (r - 1) << 1; i >= l; i --) {
		heapify(arr, i, r - 1);
	}

	for(int i = r - 1; i > l; i --) {
		swap(arr[i], arr[l]);
		heapify(arr, 0, i - 1);
	}
}

相关习题

  • (蓝桥杯) 设有 nnn 个正整数 a1...ana_1 ... a_na1​...an​ ，现将它们联接成一排，相邻数字首位相接，组成一个最大的整数。其中，1≤n≤20，1≤ai≤1091≤n≤20，1≤a_i≤10^91≤n≤20，1≤ai​≤109。 
     Input: 3           |   Input: 4
 Input: 13 312 343  |   Input: 7 13 4 246
 Output: 34331213   |   Output: 7424613

#include <vector>
#include <iostream>
#include <algorithm>

using std::vector;
using std::string;


bool comp(std::string a , std::string b) {
	return a + b > b + a;
}


int main() {
	std::ios::sync_with_stdio(false);

	int n = 0;
	std::cin >> n;
	vector<string> base;

	base.resize(n);
	for(int i = 0; i < n; i ++)
		std::cin >> base[i];
	sort(base.begin(),base.end(),comp);
	
	for(int i = 0; i < n; i ++)
		std::cout << base[i];

	return 0;
}

本题可以按照冒泡排序的思路去进行求解，既然是最大值，就说明我们任意改变这 nnn 个整数的排列顺序都不会使得这个结果更大，所以这 nnn 个整数一定不能逆序。aaa 可以放在 bbb 前，当且仅当 ab≥baab \ge baab≥ba，对于字符串而言，+++ 运算就相当于拼接，因此我们可以自定义 compcompcomp 函数。

倘若我们将整个数组由小至大排序，则第 kkk 大的元素刚好位于 length−klength - klength−k 处，因此我们可以不断调用 randomPartitionrandomPartitionrandomPartition 过程，判断我们排好的位置 indexindexindex 和目标位置 targettargettarget 的大小关系，从而决定继续操作区间的哪一部分。

int randomPartition(vector<int>& base, int l, int r) {
    srand(time(0));
    int m = rand() % (r - l + 1) + l;

    swap(base[m], base[l]);
    int i = l, j = r, divider = base[l];

    while(i < j) {
        while(base[j] >= divider && i < j) j --;
        while(base[i] <= divider && i < j) i ++;
        if(i < j) swap(base[i], base[j]);
    }

    base[l] = base[i];
    base[i] = divider;
    return i;
}


int quickSelect(vector<int>& base, int l, int r, int target) {
    int index = randomPartition(base, l, r);

    if(index == target) {
        return base[index];
    }else if(index < target) {
        return quickSelect(base, index + 1, r, target);
    }else {
        return quickSelect(base, l, index - 1, target);
    }
}


int findKthLargest(vector<int>& nums, int k) {
    int length = nums.size();
    return quickSelect(nums, 0, length - 1, length - k);
}
  • 75. 颜色分类 - 力扣（LeetCode） 回忆前文中快速排序的实现方法，我们定义了两个标记变量 i 和 j，并将它们分别置于数组的左端和右端。本题的输入只包含三种数字，且最终的排列也是固定的 [0..1..2] 形式，即 0 位于区间左侧，1 位于区间中部，2 则位于区间右侧。因此，我们仿照快速排序的实现思路，定义两个指针并将它们置于区间的两端。每次扫描到 1 则继续前进，保持 zero、two 不动；扫描到 2，则让 two 向左侧挪动一个位置，并交换 nums[i] 和 nums[two]；扫描到 0，则让 zero 向右侧挪动一个位置，交换 nums[i] 和 nums[zero]，并让 i 指向下一个未扫描元素。
void sortColors(vector<int>& nums) {
    int zero = -1, two = nums.size();

    for(int i = 0; i < two; ) {
        if(nums[i] == 1) i ++;
        else if(nums[i] == 2) {
            swap(nums[i], nums[-- two]);
        }else {
            swap(nums[i ++], nums[++ zero]);
        }
    }
}
  • 21. 合并两个有序链表 - 力扣（LeetCode） 本题非常适合利用递归求解，但是迭代的形式更容易让我们将其与归并排序联系起来。事实上，在看到题目的名称后，我们脑海中就应该自然而然地想到 mergemergemerge 过程。
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
    ListNode* pre_head = new ListNode(-1);
    
    ListNode* prev = pre_head;
    while(l1 != nullptr && l2 != nullptr) {
        if(l1->val < l2->val) {
            prev->next = l1;
            l1 = l1->next;
        }else {
            prev->next = l2;
            l2 = l2->next;
        }
        prev = prev->next;
    }
    prev->next = l1 == nullptr? l2 : l1;
    return pre_head->next;
}
转载自:https://juejin.cn/post/7056703956864466951
评论
请登录