排序算法总结：
术语说明：
- 稳定：如果a原本在b前面，而a=b，排序之后a仍然在b的前面；
- 不稳定：如果a原本在b的前面，而a=b，排序之后a可能会出现在b的后面；
- 内排序：所有排序操作都在内存中完成；
- 外排序：由于数据太大，因此把数据放在磁盘中，而排序通过磁盘和内存的数据传输才能进行；
- 时间复杂度： 一个算法执行所耗费的时间；
- 空间复杂度：运行完一个程序所需内存的大小。
Java 主要排序方法为 java.util.Arrays.sort()，对于原始数据类型使用三向切分的快速排序，对于引用类型使用归并排序
1. 冒泡排序（Bubble Sort）
冒泡排序：是一种简单的排序算法，它从左到右不断交换相邻逆序的元素，在一轮遍历后，可以让未排序部分中最大的元素浮到右侧。不多的从左到右调整，直至数组有序。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public int[] bubbleSort(int [] input){
if(input.length == 0){
return input;
}
for(int i=input.length-1; i>0; i--){
for(int j=0; j<i; j++){
if(input[j] > input[j+1]){
int temp = input[j];
input[j] = input[j+1];
input[j+1] = temp;
}
}
}
return input;
}
算法分析
- 时间复杂度： O(n^2)
- 空间复杂度： O(1)
2. 选择排序（Selection Sort）
选择排序：首先，找到数组中最小的那个元素，其次，将它和数组的第一个元素交换位置。再次，在剩下的元素中找到最小的元素，将它与数组的第二个元素交换位置。如此往复，直到将整个数组排序。
选择排序是表现最稳定的排序算法之一 ，因为无论什么数据进去都是O(n2)的时间复杂度 ，所以用到它的时候，数据规模越小越好。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public int[] selectSort(int [] input){
if(input.length == 0){
return input;
}
for(int i=0; i<input.length; i++){
int minIndex = i;
for(int j=i+1; j<input.length; j++){
if(input[j] < input[minIndex]){
minIndex = j;
}
}
int temp = input[i];
input[i] = input[minIndex];
input[minIndex] = temp;
}
return input;
}
算法分析
- 时间复杂度： O(n^2)
- 空间复杂度： O(1)
3.插入排序（Insertion Sort）
插入排序： 直接插入排序是将无序序列中的数据插入到有序的序列中，在遍历无序序列时，首先拿无序序列中的首元素去与有序序列中的每一个元素比较并插入到合适的位置，一直到无序序列中的所有元素插完为止。对于一个无序序列arr{4，6，8，5，9}来说，我们首先先确定首元素4是有序的，然后在无序序列中向右遍历，6大于4则它插入到4的后面，再继续遍历到8，8大于6则插入到6的后面，这样继续直到得到有序序列{4，5，6，8，9}。
插入排序所需的时间取决于输入中元素的初始顺序。
插入排序对于实际应用中常见的某些类型的非随机数组很有效。
插入排序对于部分有序的数组十分高效，也很适合小规模数组。
1 |
|
算法分析
- 时间复杂度: O(n^2)
- 空间复杂度: O(1)
4. 希尔排序（Shell Sort）
希尔排序：对于大规模的数组，插入排序很慢，因为它只能交换相邻的元素，每次只能将逆序数量减少 1。希尔排序的出现就是为了改进插入排序的这种局限性，它通过交换不相邻的元素，每次可以将逆序数量减少大于 1。希尔排序使用插入排序对间隔 h 的序列进行排序。通过不断减小 h，最后令 h=1，就可以使得整个数组是有序的。希尔排序的核心在于间隔序列的设定。既可以提前设定好间隔序列，也可以动态的定义间隔序列。希尔排序又叫缩小增量排序。
1 |
|
算法分析
希尔排序的运行时间达不到平方级别， 希尔排序比插入排序和选择排序要快得多，并且数组越大，优势越大。
5. 归并排序（Merge Sort）
归并排序： 是采用分治法（Divide and Conquer）的一个非常典型的应用。归并排序是一种稳定的排序方法。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为2-路归并。
算法描述
- 步骤1：把长度为n的输入序列分成两个长度为n/2的子序列；
- 步骤2：对这两个子序列分别采用归并排序；
- 步骤3：将两个排序好的子序列合并成一个最终的排序序列。
1 |
|
算法分析
归并排序是一种稳定的排序方法。和选择排序一样，归并排序的性能不受输入数据的影响，但表现比选择排序好的多，因为始终都是 O(nlogn 的时间复杂度。代价是需要额外的内存空间。
- 时间复杂度：O(nlogn)
- 空间复杂度：O(n)
6. 快速排序（Quick Sort）
快速排序：通过分割元素将待排序的序列分隔成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。
快速排序是最快的通用排序方法, 因为快速排序内循环指令少，他还能利用缓存（因为总是顺序访问数组），时间复杂度都是~cNlgN.
算法描述：
- 从数列中挑出一个元素，称为 “基准” (pivot)；
- 重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作；
- 递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序。
1 |
|
将待排序的序列分为两个部分的方法有多种：
方法一：
- 定义两个指针，begin和end分别指向第一个元素和最后一个元素，基准值key=arr[end];
- begin从前向后移动，当遇到大于key的时候停下来，end从后向前移动，当遇到小于key的时候停下，交换begin和end对应的元素；
重复上一步，直至begin与end相遇，begin对应的元素与key值进行交换。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20public int partition(int[] input, int lo, int hi){
int key = input[lo];
int key_idnex = lo;
while(lo < hi){
while(lo<hi && input[hi]>=key){
hi--;
}
while(lo<hi && input[lo]<=key){
lo++;
}
swap(input, lo, hi);
}
swap(input, key_idnex, lo);
return lo;
}
public void swap(int[] input, int i, int j){
int temp = input[i];
input[i] = input[j];
input[j] = temp;
}
方法二：挖坑法
- 定义两个指针，begin和end分别指向第一个元素和最后一个元素，基准值key=arr[end];
- begin从前向后移动，当遇到大于key的时候停下来，将begin位置的数据放置end处，begin变为坑；
- end从后开始向前移动，当遇到小于key的时候停下来，将end处的数据放置坑（begin）处，end变为坑，begin开始移动；
重复2、3两步，直至begin与end相遇，最后的一个坑放key。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15public int partition(int[] input, int lo, int hi){
int v = input[lo];
while(lo < hi){
while(lo < hi && input[hi] >= v){
hi--;
}
input[lo] = input[hi];
while(lo < hi && input[lo] <= v){
lo++;
}
input[hi] = input[lo];
}
input[lo] = v;
return lo;
}
算法分析
- 时间复杂度： 平均-O(nlogn)， 最坏-O(n^2)
- 空间复杂度： O(logn)
https://blog.csdn.net/wei_cheng18/article/details/80302818
7. 堆排序
堆排序：是指利用堆这种数据结构所设计的一种排序算法。堆这种数据结构是一种完全二叉树，堆分为最大堆和最小堆。
- 最大堆：二叉树中的任一顶点大于等于它的左右子节点
- 最小堆：二叉树中的任一顶点小于等于它的左右子节点
堆可以用数组来存储表示
7.1 算法描述
堆排序分为两个阶段，给定一个无序的数组，首先要做的事构造堆。
a.将无序输入数组构建成一个堆，根据升序降序需求选择最大堆或最小堆;
b.将堆顶元素与末尾元素交换，将最大元素”沉”到数组末端，N–，将最大的元素固定,再次调整剩余的部分，不再去管它;
c.重新调整结构，使其满足堆定义，然后继续交换堆顶元素与当前末尾元素，反复执行调整+交换步骤，直到整个序列有序。
对于给定的无序构造堆的一个高效方法就是从右向左进行sink下沉操作，不需要管叶子结点（叶子结点已经算作一个有堆，无法进行下沉操作），所以只需要扫描一半的数组元素。
算法的示意动图可参考下文：
https://blog.csdn.net/weixin_41190227/article/details/86600821
7.2 代码实现
1 |
|
算法分析：
- 时间复杂度： O(nlogn)
- 空间复杂度： 1
各个排序算法的实现
1 |
|