目录
一、排序
1.概念
2.常见的排序算法
二、常见排序算法的实现
1.插入排序
1.1直接插入排序
1.2希尔排序(缩小增量法)
1.3直接插入排序和希尔排序的耗时比较
2.选择排序
2.1直接选择排序
2.2堆排序
2.3直接选择排序与堆排序的耗时比较
3.交换排序
3.1冒泡排序
3.2快速排序
1. Hoare版
2. 挖坑法
3. 前后指针
3.2.1快速排序的优化
1.三数取中法选key
2. 递归到小的子区间时，可以考虑使用插入排序
3.2.2非递归的快速排序
4.归并排序
1.归并排序
2.非递归的归并排序
3.海量数据的排序问题
5.排序算法复杂度及稳定性分析
编辑
三、其他非基于比较排序
1.计数排序
2.基数排序
3.桶排序
4.比较
5.排序
一、排序
1.概念
所谓排序，就是使一串记录，按照其中的某个或某些关键字的大小，递增或递减的排列起来的操作。
稳定性：假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中，r[i]=r[j]，且r[i]在r[j]之前，而在排序后的序列中，r[i]仍在r[j]之前，则称这种排序算法是稳定的；否则称为不稳定的。
内部排序：数据元素全部放在内存中的排序
外部排序：数据元素太多不能同时放在内存中，根据排序过程的要求在内外存之间移动数据的排序
2.常见的排序算法
二、常见排序算法的实现
1.插入排序
把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中，直到所有的记录插入完为止，得到一个新的有序序列
1.1直接插入排序
public static void insertSort(int[] array) {
for (int i = 1; i < array.length; i++) {
int j = i - 1;
int tmp = array[i];
for (; j >= 0; j--) {
if(array[j] > tmp) {
//if(arr[j] >= tmp)
//变为不稳定的排序
array[j+1] = array[j];
}else {
// array[j+1] = tmp;
break;
}
}
array[j+1] = tmp;
}
}直接插入排序的特性总结：
1. 元素集合越接近有序，直接插入排序算法的时间效率越高
2. 时间复杂度：O(N^2)
3. 空间复杂度：O(1)，它是一种稳定的排序算法
4. 稳定性：稳定
如果一个排序 本身就是稳定的排序 那么它就可以被实现为不稳定的排序，
但是一个排序 本身就是不稳定的排序 那么它不可能被实现为稳定的排序
1.2希尔排序(缩小增量法)
先选定一个整数，把待排序文件分为整数个组，再进行每个组内的排序
跳跃式分组:
public static void shellSort(int[] array) {
int gap = array.length;
while(gap > 1) {
gap /= 2;
shell(array,gap);
}
}
private static void shell(int[] array, int gap) {
for (int i = gap; i < array.length; i++) {
int j = i - gap;
int tmp = array[i];
for (; j >= 0; j -= gap) {
if(array[j] > tmp) {
array[j+gap] = array[j];
}else {
break;
}
}
array[j+gap] = tmp;
}
} 希尔排序的特性总结：
1. 希尔排序是对直接插入排序的优化。
2. 当gap > 1时都是预排序，目的是让数组更接近于有序。当gap == 1时，数组已经接近有序的了，这样就会很快。这样整体而言，可以达到优化的效果。
3. 希尔排序的时间复杂度不固定：O(N^1.3)....O(N^1.5)
4. 空间复杂度：O(1) ，不稳定
1.3直接插入排序和希尔排序的耗时比较
import java.util.Arrays;
import java.util.Random;
public class Text {
public static void readyDataOrder(int[] array) {
Random random = new Random();
for (int i = 0; i < array.length; i++) {
array[i] = random.nextInt(100000);
}
}
public static void InsertOrder(int[] array) {
array = Arrays.copyOf(array,array.length);
long start = System.currentTimeMillis();
Sort.insertSort(array);
long end = System.currentTimeMillis();
System.out.println("插入排序耗时参考：" + (end - start));
}
public static void ShellOrder(int[] array) {
long start = System.currentTimeMillis();
Sort.shellSort(array);
long end = System.currentTimeMillis();
System.out.println("希尔排序耗时参考：" + (end - start));
}
public static void main(String[] args) {
int[] array = new int[100000];
readyDataOrder(array);
InsertOrder(array);
ShellOrder(array);
}
}
//插入排序耗时参考：1884
//希尔排序耗时参考：22
2.选择排序
每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完
2.1直接选择排序
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);
}
}
private static void swap(int[] array, int i, int minIndex) {
int tmp = array[i];
array[i] = array[minIndex];
array[minIndex] = tmp;
}直接选择排序的特性总结:
1. 直接选择排序思考非常好理解，但是效率不是很好。实际中很少使用
2. 时间复杂度：O(N^2)
3. 空间复杂度：O(1)
4. 稳定性：不稳定
private static void swap(int[] array, int i, int j) {
int tmp = array[i];
array[i] = array[j];
array[j] = tmp;
}
public static void select2Sort(int[] array) {
int left = 0;
int right = array.length - 1;
while(left<right) {
int minIndex = left;
int maxIndex = left;
for (int i = left + 1; i <= right; i++) {
if(array[i] < array[minIndex]) {
minIndex = i;
}
if(array[i] > array[maxIndex]) {
maxIndex = i;
}
}
swap(array,left,minIndex);
//第一个数据是最大值
if(maxIndex == left) {
maxIndex = minIndex;
}
swap(array,right,maxIndex);
left++;
right--;
}
}
//复杂度不变2.2堆排序
堆排序(Heapsort)是指利用堆积树（堆）这种数据结构所设计的一种排序算法，它是选择排序的一种。它是通过堆来进行选择数据。需要注意的是排升序要建大堆，排降序建小堆
public static void heapSort(int[] array) {
createHeap(array);
int end = array.length - 1;
while(end > 0) {
swap(array,0,end);
siftDown(array,0,end);
end--;
}
}
private static void swap(int[] array, int i, int j) {
int tmp = array[i];
array[i] = array[j];
array[j] = tmp;
}
public static void createHeap(int[] array) {
for (int parent = (array.length - 1 - 1) / 2; parent >= 0; parent--) {
siftDown(array,parent,array.length);
}
}
private static void siftDown(int[] array,int parent,int len) {
int child = parent * 2 + 1;
while(child < len) {
if(child + 1 < len && array[child] < array[child + 1]) {
child++;
}
if(array[child] > array[parent]) {
swap(array,child,parent);
parent = child;
child = parent * 2 + 1;
}else {
break;
}
}
}堆排序的特性总结：
1. 堆排序使用堆来选数，效率就高了很多。
2. 时间复杂度：O(N*logN)
3. 空间复杂度：O(1)
4. 稳定性：不稳定
2.3直接选择排序与堆排序的耗时比较
public class Text {
public static void main(String[] args) {
int[] array = new int[100000];
readyDataOrder(array);
InsertOrder(array);
ShellOrder(array);
selectOrder(array);
select2Order(array);
heaptOrder(array);
}
public static void readyDataOrder(int[] array) {
Random random = new Random();
for (int i = 0; i < array.length; i++) {
array[i] = random.nextInt(100000);
}
}
public static void InsertOrder(int[] array) {
array = Arrays.copyOf(array,array.length);
long start = System.currentTimeMillis();
Sort.insertSort(array);
long end = System.currentTimeMillis();
System.out.println("插入排序耗时参考：" + (end - start));
}
public static void ShellOrder(int[] array) {
array = Arrays.copyOf(array,array.length);
long start = System.currentTimeMillis();
Sort.shellSort(array);
long end = System.currentTimeMillis();
System.out.println("希尔排序耗时参考：" + (end - start));
}
public static void selectOrder(int[] array) {
array = Arrays.copyOf(array,array.length);
long start = System.currentTimeMillis();
Sort.selectSort(array);
long end = System.currentTimeMillis();
System.out.println("选择排序耗时参考：" + (end - start));
}
public static void select2Order(int[] array) {
array = Arrays.copyOf(array,array.length);
long start = System.currentTimeMillis();
Sort.select2Sort(array);
long end = System.currentTimeMillis();
System.out.println("选择排序2耗时参考：" + (end - start));
}
public static void heaptOrder(int[] array) {
array = Arrays.copyOf(array,array.length);
long start = System.currentTimeMillis();
Sort.heapSort(array);
long end = System.currentTimeMillis();
System.out.println("堆排序耗时参考：" + (end - start));
}
}
//插入排序耗时参考：2098
//希尔排序耗时参考：25
//选择排序耗时参考：4093
//选择排序2耗时参考：2929
//堆排序耗时参考：16
3.交换排序
所谓交换，就是根据序列中两个记录键值的比较结果来对换这两个记录在序列中的位置，交换排序的特点是：将键值较大的记录向序列的尾部移动，键值较小的记录向序列的前部移动。
3.1冒泡排序
public static void bubbleSort(int[] array) {
//i是趟数
for (int i = 0; i < array.length - 1; i++) {
for (int j = 0; j < array.length - 1 - i; j++) {
if(array[j] > array[j+1]) {
swap(array,j,j+1);
}
}
}
}
private static void swap(int[] array, int i, int j) {
int tmp = array[i];
array[i] = array[j];
array[j] = tmp;
}冒泡排序的特性总结：
1. 冒泡排序是一种非常容易理解的排序
2. 时间复杂度：O(N^2)
3. 空间复杂度：O(1)
4. 稳定性：稳定
优化：
public static void bubbleSort(int[] array) {
//i是趟数
for (int i = 0; i < array.length - 1; i++) {
boolean flg = true;
for (int j = 0; j < array.length - 1 - i; j++) {
if(array[j] > array[j+1]) {
swap(array,j,j+1);
flg = false;
}
}
if(flg) {
break;
}
}
}
private static void swap(int[] array, int i, int j) {
int tmp = array[i];
array[i] = array[j];
array[j] = tmp;
}3.2快速排序
任取待排序元素序列中的某元素作为基准值，按照该排序码将待排序集合分割成两子序列，左子序列中所有元素均小于基准值，右子序列中所有元素均大于基准值，然后最左右子序列重复该过程，直到所有元素都排列在相应位置上为止
1. Hoare版
public static void quickSort(int[] array) {
quick(array,0,array.length - 1);
}
private static void quick(int[] array, int left, int right) {
if(left > right) return;
int par = partition(array,left,right);
quick(array,left,par-1);
quick(array,par+1,right);
}
private static int partition(int[] array, int start, int end) {
int i = start;
int pivot = array[start];
while(start < end) {
//先end后start
while(start < end && array[end] >= pivot) {
end--;
}
while(start < end && array[start] <= pivot) {
start++;
}
swap(array,start,end);
}
swap(array,i,start);
return start;
}
private static void swap(int[] array, int i, int j) {
int tmp = array[i];
array[i] = array[j];
array[j] = tmp;
}快速排序的特性总结：
1. 快速排序整体的综合性能和使用场景都是比较好的，所以才敢叫快速排序
2. 时间复杂度：O(N*logN) 如果的是1 2 3 4 5 或 5 4 3 2 1…… 单分支的树时间复杂度为O(N^2),但一般不说快排时间复杂度为O(N^2)，
3. 空间复杂度：O(logN) 单分支的树空间复杂度为O(N)
4. 稳定性：不稳定
//插入排序耗时参考：1983
//希尔排序耗时参考：19
//选择排序耗时参考：3844
//选择排序2耗时参考：2977
//堆排序耗时参考：14
//冒泡排序耗时参考：20525
//快速排序耗时参考：112. 挖坑法
public static void quickSort(int[] array) {
quick(array,0,array.length - 1);
}
private static void quick(int[] array, int left, int right) {
if(left > right) return;
int par = partition(array,left,right);
quick(array,left,par-1);
quick(array,par+1,right);
}
private static int partition(int[] array,int start,int end) {
int pivot = array[start];
while(start < end) {
while(start < end && array[end] >= pivot) {
end--;
}
array[start] = array[end];
while(start < end && array[start] <= pivot) {
start++;
}
array[end] = array[start];
}
array[start] = pivot;
return start;
}3. 前后指针
public static void quickSort(int[] array) {
quick(array,0,array.length - 1);
}
private static void quick(int[] array, int left, int right) {
if(left > right) return;
int par = partition(array,left,right);
quick(array,left,par-1);
quick(array,par+1,right);
}
private static int partition(int[] array,int start,int end) {
int prev = start;
int cur = start + 1;
while(cur <= end) {
if(array[cur] < array[start] && array[++prev] != array[cur]) {
swap(array,cur,prev);
}
cur++;
}
swap(array,prev,start);
return prev;
}
private static void swap(int[] array, int i, int j) {
int tmp = array[i];
array[i] = array[j];
array[j] = tmp;
}3.2.1快速排序的优化
1.三数取中法选key
private static void quick(int[] array, int left, int right) {
if(left > right) return;
int index = midThreeNum(array,left,right);
swap(array,index,left);
int par = partition(array,left,right);
quick(array,left,par-1);
quick(array,par+1,right);
}
//三数取中法选key
public static int midThreeNum(int[] array, int start, int end) {
int mid = (start + end) / 2;
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;
}
}
}2. 递归到小的子区间时，可以考虑使用插入排序
public static void quickSort(int[] array) {
quick(array,0,array.length - 1);
}
private static void quick(int[] array, int left, int right) {
if(left > right) return;
if(right - left + 1 == 7) {
insertSort2(array,left,right);
}
int index = midThreeNum(array,left,right);
swap(array,index,left);
int par = partition(array,left,right);
quick(array,left,par-1);
quick(array,par+1,right);
}
//三数取中法选key
public static int midThreeNum(int[] array, int start, int end) {
int mid = (start + end) / 2;
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;
}
}
}
//递归到小的子区间时，可以考虑使用插入排序
private static void insertSort2(int[] array ,int start,int end) {
for (int i = start + 1; i <= end; i++) {
int j = i - 1;
int tmp = array[i];
for (; j >= start; j--) {
if (array[j] > tmp) {
array[j + 1] = array[j];
} else {
// array[j+1] = tmp;
break;
}
}
array[j + 1] = tmp;
}
}
private static int partition(int[] array, int start, int end) {
int i = start;
int pivot = array[start];
while(start < end) {
while(start < end && array[end] >= pivot) {
end--;
}
while(start < end && array[start] <= pivot) {
start++;
}
swap(array,start,end);
}
swap(array,i,start);
return start;
}3.2.2非递归的快速排序
public static void quickSort2(int[] array) {
int left = 0;
int right = array.length - 1;
int par = partition(array,left,right);
Stack<Integer> stack = new Stack<>();
if(par > left + 1) {
stack.push(left);
stack.push(par - 1);
}
if(par < right - 1) {
stack.push(par + 1);
stack.push(right);
}
while(!stack.isEmpty()) {
right = stack.pop();
left = stack.pop();
par = partition(array,left,right);
if(par > left + 1) {
stack.push(left);
stack.push(par - 1);
}
if(par < right - 1) {
stack.push(par + 1);
stack.push(right);
}
}
}
private static int partition(int[] array, int start, int end) {
int i = start;
int pivot = array[start];
while(start < end) {
while(start < end && array[end] >= pivot) {
end--;
}
while(start < end && array[start] <= pivot) {
start++;
}
swap(array,start,end);
}
swap(array,i,start);
return start;
}4.归并排序
归并排序（MERGE-SORT）是建立在归并操作上的一种有效的排序算法,该算法是采用分治法（Divide andConquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并
1.归并排序
public static void mergeSort(int[] array) {
mergeSortFunc(array,0,array.length - 1);
}
private static void mergeSortFunc(int[] array,int left,int right) {
if(left == right) return;
int mid =(left + right) / 2;
//分解
mergeSortFunc(array,left,mid);
mergeSortFunc(array,mid+1,right);
//合并
merge(array,left,right,mid);
}
private static void merge(int[] array, int left, int right, int mid) {
int s1 = left;
int e1 = mid;
int s2 = mid + 1;
int e2 = right;
int[] tmpArr = new int[right - left + 1];
int k = 0;
while(s1<=e1 && s2<=e2) {
if(array[s1] < array[s2]) {
tmpArr[k++] = array[s1++];
}else {
tmpArr[k++] = array[s2++];
}
}
while(s1<=e1) {
tmpArr[k++] = array[s1++];
}
while(s2<=e2) {
tmpArr[k++] = array[s2++];
}
for (int i = 0; i < tmpArr.length; i++) {
array[i+left] = tmpArr[i];
}
}归并排序的特性总结：
1. 归并的缺点在于需要O(N)的空间复杂度，归并排序的思考更多的是解决在磁盘中的外排序问题。
2. 时间复杂度：O(N*logN)
3. 空间复杂度：O(N)
4. 稳定性：稳定
//插入排序耗时参考：2301
//希尔排序耗时参考：25
//选择排序耗时参考：4710
//选择排序2耗时参考：3635
//堆排序耗时参考：25
//冒泡排序耗时参考：23906
//快速排序耗时参考：40
//归并排序耗时参考：422.非递归的归并排序
public static void mergeSort(int[] array) {
int gap = 1;
while (gap < array.length) {
for (int i = 0; i < array.length; i += 2*gap) {
int left = i;
int mid = left + gap - 1;
int right = mid + gap;
if (mid >= array.length) {
mid = array.length - 1;
}
if (right >= array.length) {
right = array.length - 1;
}
merge(array, left, right, mid);
}
gap *= 2;
}
}
private static void merge(int[] array, int left, int right, int mid) {
int s1 = left;
int e1 = mid;
int s2 = mid + 1;
int e2 = right;
int[] tmpArr = new int[right - left + 1];
int k = 0;
while (s1 <= e1 && s2 <= e2) {
if (array[s1] < array[s2]) {
tmpArr[k++] = array[s1++];
} else {
tmpArr[k++] = array[s2++];
}
}
while (s1 <= e1) {
tmpArr[k++] = array[s1++];
}
while (s2 <= e2) {
tmpArr[k++] = array[s2++];
}
for (int i = 0; i < tmpArr.length; i++) {
array[i + left] = tmpArr[i];
}
}3.海量数据的排序问题
外部排序：排序过程需要在磁盘等外部存储进行的排序
前提：内存只有 1G，需要排序的数据有 100G
因为内存中因为无法把所有数据全部放下，所以需要外部排序，而归并排序是最常用的外部排序
1. 先把文件切分成 200 份，每个 512 M
2. 分别对 512 M 排序，因为内存已经可以放的下，所以任意排序方式都可以
3. 进行 2路归并，同时对 200 份有序文件做归并过程，最终结果就有序了
5.排序算法复杂度及稳定性分析
| 排序方法 | 最好 | 平均 | 最坏 | 空间复杂度 | 稳定性 |
| 冒泡排序 | O(n) | O(n^2) | O(n^2) | O(1) | 稳定 |
| 插入排序 | O(n) | O(n^2) | O(n^2) | O(1) | 稳定 |
| 选择排序 | O(n^2) | O(n^2) | O(n^2) | O(1) | 不稳定 |
| 希尔排序 | O(n) | O(n^1.3) | O(n^2) | O(1) | 不稳定 |
| 堆排序 | O(n * log(n)) | O(n * log(n)) | O(n * log(n)) | O(1) | 不稳定 |
| 快速排序 | O(n * log(n)) | O(n * log(n)) | O(n^2) | O(log(n)) ~ O(n) | 不稳定 |
| 归并排序 | O(n * log(n)) | O(n * log(n)) | O(n * log(n)) | O(n) | 稳定 |
三、其他非基于比较排序
1.计数排序
计数排序的场景一定是数据集中在某各范围中
步骤：
1. 统计相同元素出现次数
2. 根据统计的结果将序列回收到原来的序列中
public static void countSort(int[] array) {
//1.求 最大值 最小值 来确定 计数数组的大小
int min = array[0];
int max = array[0];
for (int i = 1; i < array.length; i++) {
if(array[i] < min) {
min = array[i];
}
if(array[i] > max) {
max = array[i];
}
}
int len = max - min + 1;
int[] count = new int[len];
//2.遍历原来的数组 存放元素到计数数组中
//O(N)
for (int i = 0; i < array.length; i++) {
int index = array[i] - min;
count[index]++;
}
//3.遍历计数数组
//O(范围)
int arrIndex = 0;
for (int i = 0; i < count.length; i++) {
while(count[i]!=0) {
array[arrIndex] = i + min;
arrIndex++;
count[i]--;
}
}时间复杂度：O(范围 + N )
空间复杂度：O(范围)
稳定性：稳定
2.基数排序
动态图
队列，桶
3.桶排序
划分多个范围相同的区间，每个子区间自排序，最后合并
public static void bucketSort(int[] array){
// 计算最大值与最小值
int max = array[0];
int min = array[0];
for(int i = 1; i < array.length; i++){
if(array[i] < min) {
min = array[i];
}
if(array[i] > max) {
max = array[i];
}
}
// 计算桶的数量
int bucketNum = (max - min) / array.length + 1;
ArrayList<ArrayList<Integer>> bucketArr = new ArrayList<>(bucketNum);
for(int i = 0; i < bucketNum; i++){
bucketArr.add(new ArrayList<Integer>());
}
// 将每个元素放入桶
for(int i = 0; i < array.length; i++){
int num = (array[i] - min) / (array.length);
bucketArr.get(num).add(array[i]);
}
// 对每个桶进行排序
for(int i = 0; i < bucketArr.size(); i++){
Collections.sort(bucketArr.get(i));
}
// 将桶中的元素赋值到原序列
int index = 0;
for(int i = 0; i < bucketArr.size(); i++){
for(int j = 0; j < bucketArr.get(i).size(); j++){
array[index++] = bucketArr.get(i).get(j);
}
}
}4.比较
- 基数排序：根据键值的每位数字来分配桶；
- 计数排序：每个桶只存储单一键值；
- 桶排序：每个桶存储一定范围的数值;
