算法: 几种排序汇总备忘

简单温习几种排序算法, 备忘

简单选择排序 O(n^2)

为每一趟从待排序的数据元素中选择范围内最值元素作为首元素, 直到所有元素排完为止. 不稳定的排序.

实现:

1
2
3
4
for循环i[0 -> arr.length-1):
for循环j[i+1 -> arr.length):
找最值
找到最值后,交换arr[i], arr[j].

冒泡排序 O(n^2)

对相邻的元素进行两两比较, 时而交换, 每一趟会将范围内最值元素冒到顶端.

实现:

1
2
3
4
5
6
7
for循环i[0 -> arr.length-1):
flag = false;
for循环j[0 -> arr.length-1-i):
arr[j],arr[j+1]顺序若不符合:
交换arr[j],arr[j+1].
flag = true;
if(flag) break;

直接插入排序 O(n^2)

每一步将一个待排序的记录, 插入到前面已经排好序的有序序列中, 直到插完所有元素为止.

实现:

1
2
3
4
5
for循环i[1 -> arr.length):
j = i;
while(j > 0 && arr[j] < arr[j-1]):
交换arr[j],arr[j-1].
j--;

希尔排序

把记录按下标的一定增量分组, 对每组使用直接插入排序算法排序. 随着增量逐渐减少, 每组包含的关键词越来越多, 当增量减至1时, 整个文件恰被分成一组, 算法便终止.

相对于插入排序来讲, 减少了元素移动和比较的次数.

交换插入实现:

1
2
3
4
5
6
7
8
9
10
11
12
//增量gap,并逐步缩小增量
for(int gap=arr.length/2;gap>0;gap/=2){
//从第gap个元素,逐个对其所在组进行直接插入排序操作
for(int i=gap;i<arr.length;i++){
int j = i;
while(j-gap>=0 && arr[j]<arr[j-gap]){
//插入排序采用交换法
swap(arr,j,j-gap);
j-=gap;
}
}
}

移动插入实现:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
 //增量gap,并逐步缩小增量
for(int gap=arr.length/2;gap>0;gap/=2){
//从第gap个元素,逐个对其所在组进行直接插入排序操作
for(int i=gap;i<arr.length;i++){
int j = i;
int temp = arr[j];
if(arr[j]<arr[j-gap]){
while(j-gap>=0 && temp<arr[j-gap]){
//移动法
arr[j] = arr[j-gap];
j-=gap;
}
arr[j] = temp;
}
}
}

堆排序

堆排序是利用堆这种数据结构而设计的一种排序算法, 堆排序是一种选择排序, 它的最坏, 最好, 平均时间复杂度均为O(nlogn). 不稳定排序。

堆利用了完全二叉树的性质. 且一般使用数组来实现, 并且满足一定的约束条件:

大顶堆: arr[i] >= arr[2i+1] && arr[i] >= arr[2i+2]
小顶堆: arr[i] <= arr[2i+1] && arr[i] <= arr[2i+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
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
package com.hongyan.learn.test.dataStructures;

import org.junit.Test;

import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;

/**
* @author weihongyan
* @implNote <(▰˘◡˘▰)>
* @since 30/11/2017 6:54 PM
*/
public class HeapSort {

@Test
public void test() {
int[] nums = { 6, 6, 1, 4, 5, 7, 6, 8, 3, 4, 2, 9, 0, 1, 2, -1, -4, 0, -5, 10 };
this.heapSort(nums);
System.out.println(Arrays.toString(nums));
System.out.println(topKByPriorityQueue(nums, 8));
System.out.println(topKByHeap(nums, 8));
}

public void heapSort(int[] arr) {
// 构建堆
buildMaxHeap(arr);
// 取最值 放最后 调整堆
heapAdjust(arr);
}

private void heapAdjust(int[] arr) {
for (int i = arr.length - 1; i > 1; i--) {
// 把最值与最后面交换,
swap(arr, 0, i);
// 调整元素位置
down(arr, 1, i);
}
}

private void buildMaxHeap(int[] arr) {
// 从第一个非叶子节点开始
for (int i = arr.length / 2; i > 0; i--) {
// 下滤
down(arr, i, arr.length);
}
}

// 交换用
private void swap(int[] arr, int a, int b) {
int temp = arr[a];
arr[a] = arr[b];
arr[b] = temp;
}

// 尾递归的下滤
private void down(int[] arr, int index, int length) {
// 基准情况
if (index * 2 > length || index <= 0 || length > arr.length) {
return;
}
// 偶数个节点时 最后元素特殊处理一下
if (index * 2 == length) {
if (arr[index - 1] < arr[2 * index - 1]) {
swap(arr, index - 1, 2 * index - 1);
return;
}
} else {
// 找到更大的子节点
int bigger = 0;
if (arr[2 * index - 1] >= arr[2 * index]) {
bigger = 2 * index;
} else {
bigger = 2 * index + 1;
}

if (arr[bigger - 1] > arr[index - 1]) {
// 与更大的子节点交换
swap(arr, bigger - 1, index - 1);
// 递归交换后的位置
down(arr, bigger, length);
}
}
}

/*---------------------------------------------------------------------------------------------*/


// 优先队列解topk问题
private int topKByPriorityQueue(int[] arr, int k) {
PriorityQueue<Integer> heap = new PriorityQueue<>(Comparator.comparingInt(o -> o));
for (int num : arr) {
if (heap.size() < k) {
heap.offer(num);
} else if (heap.peek() < num) {
heap.poll();
heap.offer(num);
}
}
return heap.peek();
}

// 堆解决topk问题
private int topKByHeap(int[] arr, int k) {
int[] heap = Arrays.copyOfRange(arr, 0, k);
buildMaxHeap(heap);
for (int i = k; i < arr.length; i++) {
int num = arr[i];
if (num < heap[0]) {
heap[0] = num;
down(heap, 1, heap.length);
}
}
return heap[0];
}
}

归并排序

分治思想的排序. 稳定的排序

实现:

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
public static void sort(int []arr){
//在排序前,先建好一个长度等于原数组长度的临时数组,避免递归中频繁开辟空间
int []temp = new int[arr.length];
sort(arr,0,arr.length-1,temp);
}

private static void sort(int[] arr,int left,int right,int []temp){
if(left<right){
int mid = (left+right)/2;
//左边归并排序,使得左子序列有序
sort(arr,left,mid,temp);
//右边归并排序,使得右子序列有序
sort(arr,mid+1,right,temp);
//将两个有序子数组合并操作
merge(arr,left,mid,right,temp);
}
}

private static void merge(int[] arr,int left,int mid,int right,int[] temp){
int i = left;//左序列指针
int j = mid+1;//右序列指针
int t = 0;//临时数组指针
while (i<=mid && j<=right){
if(arr[i]<=arr[j]){
temp[t++] = arr[i++];
}else {
temp[t++] = arr[j++];
}
}
//将左边剩余元素填充进temp中
while(i<=mid){
temp[t++] = arr[i++];
}
//将右序列剩余元素填充进temp中
while(j<=right){
temp[t++] = arr[j++];
}
t = 0;
//将temp中的元素全部拷贝到原数组中
while(left <= right){
arr[left++] = temp[t++];
}
}

快速排序

通过一趟排序将要排序的数据分割成独立的两部分, 然后再按此方法对这两部分数据分别进行快速排序, 整个排序过程递归进行, 以此达到整个数据变成有序序列.

实现:

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
private void recor(Integer[] nums, int start, int end) {
// 记得基准情况
if (start >= end) {
return;
}
// find middle location
Integer middle = quicksort(nums, start, end);
this.recor(nums, start, middle - 1);
this.recor(nums, middle + 1, end);
}

// 调整位置
private Integer quicksort(Integer[] nums, int low, int high) {
// key value
Integer key = nums[low];
Integer temp = null;
while (low < high) {
while (nums[high] >= key && low < high) {
high--;
}
temp = nums[high];
nums[high] = nums[low];
nums[low] = temp;
while (nums[low] <= key && low < high) {
low++;
}
temp = nums[high];
nums[high] = nums[low];
nums[low] = temp;
}
return high;
}