# 各排序算法比较
排序方法 | 时间复杂度(平均) | 时间复杂度(最坏) | 时间复杂度(最好) | 空间复杂度 | 稳定性 |
---|---|---|---|---|---|
冒泡排序 | O(n2) | O(n2) | O(n) | O(1) | 稳定 |
插入排序 | O(n2) | O(n2) | O(n) | O(1) | 稳定 |
选择排序 | O(n2) | O(n2) | O(n2) | O(1) | 不稳定 |
归并排序 | O(nlog2n) | O(nlog2n) | O(nlog2n) | O(n) | 稳定 |
快速排序 | O(nlog2n) | O(n2) | O(nlog2n) | O(nlog2n) | 不稳定 |
堆排序 | O(nlog2n) | O(nlog2n) | O(nlog2n) | O(1) | 不稳定 |
# 冒泡排序
冒泡排序的本质在于交换,即每次通过交换把当前剩余元素的最大值移动到一端,而当剩余元素减少到0时,排序结束。
public void bubbleSort(int[] nums){
int n = nums.length;
for(int i = 0; i < n - 1; i++){ // 进行n-1趟上浮,每趟上浮产生剩余元素的最大值
for(int j = 1; j < n - i; j++){ // 上浮过程,当前剩余元素为n-i个,将最大值上浮
if(nums[j-1] > nums[j]){
int temp = nums[j];
nums[j] = nums[j-1];
nums[j-1] = temp;
}
}
}
}
2
3
4
5
6
7
8
9
10
11
12
# 插入排序
对序列nums[0, n-1]中,令i从1到n-1枚举,进行n-1趟操作。假设每一趟,序列nums中前i个元素nums[0, i-1]已经有序,而nums[i, n-1]无序,将nums[i]插入到[0, i-1],使得[0,i]有序。i从1枚举到n-1,重复插入,排序完成。
public void insertSort(int[] nums){
int n = nums.length;
for(int i = 1; i < n; i++){ //n-1趟插入,将nums[i]插入到已排序好的序列nums[0, i-1]中
int temp = nums[i];
int j = i;
while(j > 0 && temp < nums[j-1]){ //将大于nums[i]的数往后移一位,空出位置插入nums[i]
nums[j] = nums[j-1];
j--;
}
nums[j] = temp;
}
}
2
3
4
5
6
7
8
9
10
11
12
# 选择排序
对序列nums中的元素nums[0,n-1],令i从[0,n-1]枚举,进行n趟操作,每趟从待排序部分[i,n-1]中选择最小的元素,令其与待排序部分的第一个元素nums[i]进行交换,这样元素nums[i]就会与当前有序区间nums[0, i-1]形成新的有序区间[0, i],在n趟操作过后,所有的元素就是有序的了。
public void selectSort(int[] nums){
int n = nums.length;
for(int i = 0; i < n; i++){ //n趟操作
int k = i;
for(int j = i+1; j < n; j++){ // 寻找[i,n-1]中最小元素的下标k
if(nums[k] > nums[j]){
k = j;
}
}
int temp = nums[i]; // 将最小元素交换到索引i处,注意到[0, i-1]始终是有序的
nums[i] = nums[k];
nums[k] = temp;
}
}
2
3
4
5
6
7
8
9
10
11
12
13
14
# 归并排序
使用递归反复将当前区间[left, right]分为两半,在对两个子区间[left, mid]和[mid+1, right]分别递归进行归并排序,然后将两个有序子区间合并为即可,递归的终止条件为left >= right,即当前区间元素为0个或者1个是不需要进行归并。
int[] temps;
@Test
public void testMergeSort(){
int[] nums = new int[]{3,4,2,5,6};
int n = nums.length;
temps = new int[n];
mergeSort(nums, 0, n-1);
Assert.assertArrayEquals(new int[]{2,3,4,5,6}, nums);
}
// 将nums数组当前区间[left, right]进行归并排序
public void mergeSort(int[] nums, int left, int right){
// 当区间内的元素个数小于或等于1的时候,这时候直接返回
if(left >= right) // 若写为left > right,当left == right时,mid将不更新,导致无限递归下去,直至栈溢出。
return ;
int mid = left + (right - left) / 2;
mergeSort(nums, left, mid); // 不能这样划分:(left,mid-1),(mid, right),因为整型除法向下取整
mergeSort(nums, mid + 1, right); // 如果是(left,right)=(0,1)那么就会划分为(0,-1)(0,1)导致无限递归
merge(nums, left, mid, mid + 1, right);
}
// 将nums的有序区间[l1, r1]与[l2, r2]合并
private void merge(int[] nums, int l1, int r1, int l2, int r2) {
int index = l1;
int start = l1;
while(l1 <= r1 && l2 <= r2){
// 写成"<="而不是"<"是为了保证归并排序的稳定性
if(nums[l1] <= nums[l2]){
temps[index++] = nums[l1++];
}else{
temps[index++] = nums[l2++];
}
}
while(l1 <= r1)
temps[index++] = nums[l1++];
while(l2 <= r2)
temps[index++] = nums[l2++];
for(int i = start; i <= r2; i++){
nums[i] = temps[i];
}
}
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
# 快速排序
要实现快速排序算法,首先要实现这样一个问题:对于一个序列nums[0, n-1],调整序列中元素的位置,使得nums[0]的左侧所有元素都不超过nums[0]、右侧所有元素都大于nums[0]。例如对序列{5,3,9,6,4,1}来说,可以调整序列中元素的位置,形成新的序列{3,1,4,5,9,6},此时元素5的左边所有元素都不超过它、右侧的所有元素都大于它,显然,元素5经过调整后就无需在调整了,因为它已经在最后有序序列的最终位置了。
接下来是快速排序的思路
(1)调整序列中的元素,使当前序列中最左端的元素在调整后满足左侧所有元素都不超过该元素、右侧所有元素都大于它。
(2)对该元素的左侧和右侧分别递归进行(1)调整,直到当前调整的区间长度不超过1。
@Test
public void testQuickSort(){
int[] nums = new int[]{5,4,2,3,5};
int n = nums.length;
quickSort(nums, 0, n-1);
Assert.assertArrayEquals(new int[]{2,3,4,5,5}, nums);
}
public void quickSort(int[] nums, int left, int right){
if(left >= right)
return;
int pos = partition(nums, left, right); // 根据pos划分左右两个子区间
quickSort(nums, left, pos - 1);
quickSort(nums, pos + 1, right);
}
// 使用nums[left]对区间[left, right]进行划分,返回nums[left]元素最终所在的位置索引
private int partition(int[] nums, int left, int right) {
int temp = nums[left];
while(left < right){
while(left < right && nums[right] > temp) right--;
nums[left] = nums[right];
while(left < right && nums[left] <= temp) left++; // 少了等于号遇到nums[left] == nums[right]时将导致死循环
nums[right] = nums[left];
}
nums[left] = temp;
return left;
}
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
当序列中元素接近有序时,不管是倒序还是升序,会达到最坏时间复杂度O(n2),产生这种情况的主要原因在于我们每次选择的主元nums[left]没有把当前区间划分为两个长度接近的子区间,这会导致递归的深度达到n而不是log2n。
# 堆排序
堆是什么?
堆是一个完全二叉树,根据结点的值与其左右孩子的值的大小关系分为大小顶堆。
- 大顶堆:树中每个结点的值都不小于其左右孩子结点的值,因此,大顶堆中,每个结点的值都是以它为根结点的子树的最大值。
- 小顶堆:树中每个结点的值都不大于其左右孩子结点的值,因此,小顶堆中,每个结点的值都是以它为根结点的子树的最小值。
由于堆是一个完全二叉树,可以使用数组去模拟这颗树,对于含有n个结点的堆来说,按照层序遍历的方式放在一个数组heap[0, n-1]中,对于数组下标为i的结点,其父亲结点所在的数组下标为(i - 1) / 2
, 其左右孩子所在的数组下标分别在i * 2 + 1
和i * 2 + 2
。
对于一个给定的初始序列,如何构建一个大顶堆?
回看大顶堆的定义,树中每个结点的值都不小于其左右孩子结点的值,对于结点i,将其往下调整,将它的值与左右孩子比较(如果有的话),若孩子中存在权值比结点的权值大的,就将其中权值最大的那个孩子结点与结点i交换;交换完毕后继续让结点i和新的孩子比较,直到结点i的权值都比左右孩子的权值大或者结点i不存在孩子。
/**
* 对head数组的head[low]元素在[low, high]范围内进行向下调整
* @param low 为欲调整结点的数组下标
* @param high 为最大能调整到的数组下标
*/
public void downAdjust(int low, int high){
int i = low; // 当前要调整的结点
int j = low * 2 + 1; // 左儿子结点索引
while(j <= high){
if(j + 1 <= high && heap[j] < heap[j+1]){
j += 1;
}
if(heap[i] < heap[j]){
int temp = heap[i];
heap[i] = heap[j];
heap[j] = temp;
i = j;
j = i * 2 + 1;
}else{
break;
}
}
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
建堆,从后往前遍历,对于结点i,i之后的结点都已经调整完毕,这就保证每个结点都是以其为根结点的子树中的权值最大的结点。
public void createHeap(){
// (n-2)/2是拥有最后一个孩子结点的父亲结点位置
for (int i = (n-2)/2; i >= 0; i--) {
downAdjust(i, n-1);
}
}
2
3
4
5
6
// 删除栈顶元素
public void deleteTop(){
heap[0] = heap[--n];
downAdjust(0, n-1);
}
2
3
4
5
/**
* 对head数组的head[high]元素在[low, high]范围内进行向上调整
* @param low 为能调整到的最小数组下标
* @param high 为欲向上调整结点的数组下标
*/
public void upAdjust(int low, int high){
int i = high; // 欲调整结点的索引
int j = (i - 1) / 2; // 其父亲结点所在的索引
while(j >= low){ // 还有父亲
if(heap[j] < heap[i]){
int temp = heap[i];
heap[i] = heap[j];
heap[j] = temp;
i = j;
j = (i - 1) / 2;
}else{
break;
}
}
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
// 插入元素
void insert(int x){
heap[n++] = x;
upAdjust(0, n-1);
}
2
3
4
5
// 堆排序
void sort(){
createHeap();
for(int i = n - 1; i > 0; i--){
int temp = heap[i];
heap[i] = heap[0];
heap[0] = temp;
downAdjust(0, i-1);
}
}
2
3
4
5
6
7
8
9
10
堆排序的时间复杂度是O(nlog2n),删除栈顶元素和插入元素的时间复杂度都是O(log2n),堆应用于优先队列的实现。
不考虑插入元素,堆排序的核心方法是downAdjust()
。
图片来源:十大经典排序算法(动图演示)
# 外部排序
# 二路合并排序
有一个含有6000个记录的文件需要排序,假定系统仅能提供容纳1800个记录的内存,如何将6000个记录进行排序?
首先将6000个文件分为5块,每块1200个记录,然后依次将这5块记录放入内存进行排序,然后写入外存,这样就得到5块排序好的记录,假设块号为1-5。
然后将内存平均分为3个缓冲区,每个缓冲区400个记录,两个缓冲区作为输入缓冲区,一个作为输出缓冲区,将块号为1的记录的前400个记录写入到第一个缓冲区,将块号为2的记录的前400个记录写入到第二个缓冲区,然后对这两块记录归并排序,如果输出缓冲区满了就写出到外存,如果输入缓冲区空了就从外存中读入(读对应的块,比如第一个缓冲区读第一块,第二个缓冲区读第二块),最后就得到一个800个排好序的记录,接下来的排序也是这样的思想,最终得到一个6000个排好序的记录。