一、排序的概念和分类
1.排序的基本概念
排序是将一批无序的记录(数据)重新排列成按关键字有序的记录序列的过程。
排序分为内部排序和外部排序
- 若整个排序过程不需要访问外存便能完成，则称此类排序问题为内部排序。
- 反之，若参加排序的记录数量很大，整个序列的排序过程不可能在内存中完成，则称此类排序问题为外部排序。
内部排序的过程是一个逐步扩大记录的有序序列长度的过程
2.排序的稳定性
假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中，r[i]=r[j]，且r[i]在r[j]之前，而在排序后的序列中，r[i]仍在r[j]之前，则称这种排序算法是稳定的；否则称为不稳定的。
总结起来就是，如果一个数据在排序过程中发生了跳跃行为，则为不稳定的排序；反之，则是稳定的排序。
- 时间复杂度：一个算法执行所耗费的时间
- 空间复杂度：运行完一个程序所需的内存大小。
二、常见排序
1.直接插入排序
直接插入排序的基本操作是讲一个记录插入到已经排好序的有序表中，从而得到一个新的、记录数增1的有序表。
代码：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
|
public static void insertSort(int[] array) {
for (int i = 1; i < array.length; i++) {
int tmp = array[i];
int j = i-1;
for (; j >= 0 ; j--) {
if(array[j] > tmp) {
array[j+1] = array[j];
}else {
break;
}
}
//j回退到了小于0的地方
array[j+1] = tmp;
}
}
|
流程图解：
时间和复杂度分析： 我们在实现的这个排序算法的时候，只借助了一个辅助的记录空间。
所以最好的情况就是我们原来需要的排序的元素之间就是有序的，比如说{1，2，3，4，5，6}，那么我们需要比较的次数，其实就是临近两个元素的比较，因此没有移动的记录，时间复杂度为O(n)；
最坏的情况就是元素都是逆序的，如{6，5，4，3，2，1}，所以都需要比较，移动次数达到O（n^2）.
稳定性：稳定
插入排序，初始数据越接近有序，时间效率越高
2.希尔排序
希尔排序法又称缩小增量法。希尔排序法的基本思想是：先选定一个整数，把待排序文件中所有记录分成个组，所有距离为的记录分在同一组内，并对每一组内的记录进行排序。然后，重复上述分组和排序的工作。当到达=1时，所有记录在统一组内排好序。
希尔对记录的分组，不是简单地“逐段分割”，而是将相隔某个“增量”的记录分成一组。
在严薇敏的《数据结构》里面是这样说的：
上面的话可能有点难理解，下面我们通过画图来了解一下希尔排序的本质。
希尔排序跟直接插入排序有点相似，可以说是直接插入排序的升级版。不同在于，希尔排序的比较方式变成了跳跃式的。比如说下面这组数据的第一次排序。
最终排序完成了。
我们来看一下希尔排序的代码：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
|
public static void shell(int[] array,int gap) {
for (int i = gap; i < array.length; i++ ) {
int tmp = array[i];
int j = i-gap;
for (; j >= 0 ; j -= gap) {
if(array[j] > tmp) {
array[j+gap] = array[j];
}else {
break;
}
}
array[j+gap] = tmp;
}
}
//按照5、3、1分组
public static void shellSort1(int[] array) {
int[] drr = {5,3,1};
for (int i = 0; i < drr.length; i++) {
shell(array,drr[i]);
}
}
|
是不是跟直接插入排序很像？所以我们才说，希尔排序是直接插入排序的升级版。它不是随便分组后各自排序，而是将相隔某个增量gap的记录组成一个子序列，实现跳跃式移动，使得排序的效率提高了。
所以，选取“增量”是非常关键的一步，值得一提的是，选取什么样的“增量”，目前为止尚没有一个没完美的增量序列。
复杂度分析：
- 时间复杂度[和增量有关系的]：O(n^1.3 - n^1.5)。
- 空间复杂度：O(1)
稳定性：不稳定的。
3.简单选择排序
简单选择排序：通过n-i次关键字间的比较，从n-i+1个记录中选出关键字最小的记录，并和第 i(1 ≤ i ≤n) 个记录交换
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
|
public static void selectSort1(int[] array) {
for (int i = 0; i < array.length; i++) {
for (int j = i+1; j < array.length; j++) {
//1 2 3 4 5 6
if(array[j] < array[i]) {
swap(array,i,j);
}
}
}
}
public static void swap(int[] array,int i,int j) {
int tmp = array[i];
array[i] = array[j];
array[j] = tmp;
|
有时候，我们可能不需要循环那么多次，循环一两次就有序了，如果在有序的序列中继续循环，则会造成时间的浪费。为避免这种情况，所以我们可以对代码进行稍稍改进：
|
1
2
3
4
5
6
7
8
9
10
11
12
|
public static void selectSort(int[] array) {
for (int i = 0; i < array.length; i++) {
int minIndex = i;
for (int j = i+1; j < array.length; j++) {
//找到最小值下标
if(array[j] < array[minIndex]) {
minIndex = j;
}
}
swap(array,i,minIndex);
}
}
|
复杂度分析：
- 时间复杂度：O(n^2)
- 空间复杂度：同接下介绍的冒泡排序一样，只有在两个记录交换时需要一个辅助空间，所以空间复杂度为O(1).
稳定性：稳定
4.堆排序
堆排序的基本原理也是选择排序，只是不在使用遍历的方式查找无序区间的最大的数，而是通过堆来选择无序区间的最大的数。
我上一篇文章有详细介绍，这里就不再说了，大家感兴趣可以去了解一下。 Java数据结构之优先级队列(堆)图文详解
这里也给一下代码：
|
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
|
public static void heapSort(int[] array) {
//1、建堆 O(N)
createHeap(array);
int end = array.length-1;
//2、交换然后调整 O(N * log N)
while (end > 0) {
swap(array,0,end);
shiftDown(array,0,end);
end--;
}
}
public static void createHeap(int[] array) {
for (int parent = (array.length-1-1)/2; parent >= 0 ; parent--) {
shiftDown(array,parent,array.length);
}
}
public static void shiftDown(int[] array,int parent,int len) {
int child = 2*parent+1;//左孩子下标
while (child < len) {
if(child+1 < len && array[child] < array[child+1]) {
child++;
}
//child下标 就是左右孩子最大值的下标
if(array[child] > array[parent]) {
swap(array,child,parent);
parent = child;
child = 2*parent+1;
}else {
break;
}
}
}
|
复杂度分析：
- 时间复杂度：O(n * log2(n))——2指的是以2为底
- 空间复杂度：O(1)
稳定性：不稳定
【注意】
- 堆排序只能用于顺序结构，不能用于链式结构
- 由于建初堆的时候所需比较的次数较多，因此记录次数较少时不宜采用。
5.冒泡排序
冒泡排序是一种交换排序，它的基本思想是：两两比较相邻记录的关键字，如果反序则交换，直到没有反序的记录为止。
代码：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
|
public static void bubbleSort(int[] array) {
for (int i = 0; i < array.length-1; i++) {
for (int j = 0; j < array.length-1; j++) {
if(array[j] > array[j+1]) {
swap(array,j+1,j);
}
}
}
}
public static void swap(int[] array,int i,int j) {
int tmp = array[i];
array[i] = array[j];
array[j] = tmp;
|
复杂度分析：
稳定性：稳定。
6.快速排序
6.1.递归快速排序
快速排序是冒泡排序的升级版，它们都属于交换排序类，即它也是通过不断比较和移动交换来实现排序，不同的是，快排的实现增大的了记录的比较和移动的距离。
快排将关键字较大的数据从前面直接移到后面，关键字较小的记录从后面直接移到前面，从而减少了总的比较次数和移动交换次数。
快排的基本思想：
通过一趟排序将待排序的数据分割成独立的两部分，其中一部分比另一部小，然后再分别对这两部分记录并再次进行排序，以达到整个序列有序。
我们翻译翻译一下上面的那段话：
- 首先，你得有一个中间数，比它小的放一边，比它大的放一边。这个数，我们称为基准值。
- 采用分治思想，对左右两个小区间按照同样的方式处理，直到小区间的长度 == 1，代表已经有序，或者小区间的长度 == 0，代表没有数据。
可能大家看到这里也还是有点迷惑，我们直接上代码。
|
1
2
3
4
5
6
7
8
9
10
11
12
|
public static void quickSort(int[] array) {
quick(array,0,array.length-1);
}
public static void quick(int[] array,int left,int right) {
if(left >= right) {
return;
}
int pivot = partition(array,left,right);//基准
quick(array,left,pivot-1);
quick(array,pivot+1,right);
}
|
上面的代码是不是有点像二叉树的遍历？
这二者确实有相似之处，我们后面再讲。
上面还有一个partition函数，这个函数是我们快速排序最关键的地方。
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
|
/**
* 找基准
* @param array 待排序数组对象
* @param start左边界
* @param end右边界
* @return 基准值下标
*/
private static int partition(int[] array,int start,int end) {
int tmp = array[start];
while (start < end) {
while (start < end && array[end] >= tmp) {
end--;
}
//end下标就遇到了 < tmp的值
array[start] = array[end];
while (start < end && array[start] <= tmp) {
start++;
}
//start下标就遇到了 > tmp的值
array[end] = array[start];
}
array[start] = tmp;
return start;
}
|
我们下面通过图解模拟一下函数的运行过程：
可以看到，当第一轮走完之后，数据由基准值分成了两部分。
之后，我们再次对左右两部分完成同样的操作，如下：
一直递归下来，跟二叉树的遍历类似。
复杂度分析：
时间复杂度：
- 最好情况下：O（nlogn）
- 最坏情况下：O（n^2）.
空间复杂度：O（logn）
稳定性：不稳定
不知大家看上面的图解的时候有没有一点困惑，就是我们这基准选得不好，导致第一趟递归下来的效果不好，变成了如下图：
如果我们有一种办法，先找到相对居中的那个数字，那么整个排序的时间复杂度是不是大大减小了。
于是，有人提出了随机选取一个值来作为基准，称为随机选取法。
这种做法，得看运气，因为假如选的好，刚刚选取中间值，那么，性能大大提高；如果随机得不好，比如随机到最小值或者最大值，那么性能则变成最差了。
所以有人提出一个新的方法，三数取中：
取三个关键字先进行排序，将中间数作为基准，一般取左端，右端和中间三个数。
如果运用三数取中这种方法的话，第一次比较的结果如下：
可以看到，11基本上与中间的数字相差不远了，性能大大提高。
所以，这里我们再写一个找基准的代码：
|
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
|
/**
* 找基准 三数取中法
* @param array 待排序数组对象
* @param left 左边界
* @param right 右边界
* @return 基准值下标
*/
private static int findMidValIndex(int[] array,int start,int end) {
int mid = start + ((end-start) >>> 1);
if(array[start] < array[end]) {
if(array[mid] < array[start]) {
return start;
}else if(array[mid] > array[end]) {
return end;
}else {
return mid;
}
}else {
if(array[mid] > array[start]) {
return start;
}else if(array[mid] < array[end]) {
return end;
}else {
return mid;
}
}
}
|
前面quick函数改动一下，如下：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
|
public static void quick(int[] array,int left,int right) {
if(left >= right) {
return;
}
//采用三数取中法找基准值
int midValIndex = findMidValIndex(array,left,right);
swap(array,midValIndex,left);
int pivot = partition(array,left,right);//基准
quick(array,left,pivot-1);
quick(array,pivot+1,right);
}
|
其实，优化到这里已经很棒了 。但是，我们还能优化。
这里先插播一个知识点：
直接插入是简单排序中性能最好的。 所以如果要我们要排序的数组非常小，直接插入排序会更好。 原因在于，快速排序用到了递归操作，在大量的数据排序时，这点性能影响相对它的整体算法优势而言是可以忽略的。但是如果数组只有不多的数据需要排序，就有点大材小用了。
因此，我们在这里的优化是：
增加一个判断，当 right-left+1 不大于某个常数时，就用直接插入排序，这个常数是具体情况而定。这样我们就能保证最大化地利用两种排序的优势来完成排序工作了。
|
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
|
/**
* 优化，加入插入排序
* @param array 待排序数组对象
* @param left 左边界
* @param right 右边界
* @return 基准值下标
*/
public static void quick(int[] array,int left,int right) {
if(left >= right) {
return;
}
//加一个判断，如果区间内的数据，在排序的过程当中，小于某个范围了，可以使用直接插入排序
if(right-left+1 <= 1400) {
//使用直接插入排序
insertSort2(array,left,right);
return;
}
//1、找基准之前，我们找到中间大小的值-使用三数取中法
int midValIndex = findMidValIndex(array,left,right);
swap(array,midValIndex,left);
int pivot = partition(array,left,right);//基准
quick(array,left,pivot-1);
quick(array,pivot+1,right);
}
//插入排序
public static void insertSort(int[] array,int start,int end) {
for (int i = 1; i <= end; i++) {
int tmp = array[i];
int j = i-1;
for (; j >= start ; j--) {
if(array[j] > tmp) {
array[j+1] = array[j];
}else {
break;
}
}
array[j+1] = tmp;
}
}
|
6.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
|
/**
* 快速排序非递归实现
* @param array 待排序数组
*/
public static void quickSort(int[] array) {
Stack<Integer> stack = new Stack<>();
int left = 0;
int right = array.length-1;
int pivot = partition(array,left,right);
if(pivot > left+1) {
stack.push(left);
stack.push(pivot-1);
}
if(pivot < right-1) {
stack.push(pivot+1);
stack.push(right);
}
while (!stack.isEmpty()) {
right = stack.pop();
left = stack.pop();
pivot = partition(array,left,right);
if(pivot > left+1) {
//左边有2个元素
stack.push(left);
stack.push(pivot-1);
}
if(pivot < right-1) {
//右边有2个元素
stack.push(pivot+1);
stack.push(right);
}
}
}
|
非递归复杂度分析：
时间复杂度：
- 最坏情况下： O(n^2)
- 平均情况下：O（nlogn）
空间复杂度：
稳定性：不稳定
7.归并排序
归并排序（MERGE-SORT）是建立在归并操作上的一种有效的排序算法,该算法是采用分治法（Divide an Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并
7.1.递归归并排序
直接上代码：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
|
//调用了mergeSortInternal函数
public static void mergeSort1(int[] array) {
mergeSortInternal(array,0,array.length-1);
}
private static void mergeSortInternal(int[] array,int low,int high) {
if(low>=high) {
return;
}
int mid = low + ((high-low) >>> 1);//>>>无符号右移1位。就是除以2，找中间值
//左边递归
mergeSortInternal(array,low,mid);
//右边递归
mergeSortInternal(array,mid+1,high);
//合并两边数组
merge(array,low,mid,high);
}
|
mergeSortInternal函数的图解：
其实就是对半分开数组
这里这个merge函数是归并排序里面的关键，无论是采用递归还是非递归都必须采用到这部分的函数。
而其本质，其实就是合并两个数组，并使其有序起来。
merge函数的代码：
|
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
|
private static void merge(int[] array,int low,int mid,int high) {
int[] tmp = new int[high-low+1];
int k = 0;//
int s1 = low;
int e1 = mid;
int s2 = mid+1;
int e2 = high;
while (s1 <= e1 && s2 <= e2) {
if(array[s1] <= array[s2]) {
tmp[k++] = array[s1++];
}else {
tmp[k++] = array[s2++];
}
}
while (s1 <= e1) {
tmp[k++] = array[s1++];
}
while (s2 <= e2) {
tmp[k++] = array[s2++];
}
//拷贝tmp数组的元素 放入原来的数组array当中
for (int i = 0; i < k; i++) {
array[i+low] = tmp[i];
}
}
|
7.2.非递归归并排序
归并排序除了用递归的方式来实现，也可以用非递归的方式来实现。
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
|
public static void mergeSort(int[] array) {
int nums = 1;//每组的数据个数
while (nums < array.length) {
//数组每次都要进行遍历,确定要归并的区间
for (int i = 0; i < array.length; i += nums*2) {
int left = i;
int mid = left+nums-1;
//防止越界
if(mid >= array.length) {
mid = array.length-1;
}
int right = mid+nums;
//防止越界
if(right >= array.length) {
right = array.length-1;
}
//小标确定之后，进行合并
merge(array,left,mid,right);
}
nums *= 2;数组合并后，以1-2-4-8-16-进行循环
}
}
|
图解如下：
总结
这次常见排序的文章，来来回回写了两天左右，在写的过程，也是学习的过程，特别是里面画图的时候，得理清楚整个排序的思想，才能很好的作出整个图解出来。各位看客老爷们，希望看到能给个三连，感谢！
