经典的排序算法总结
冒泡排序算法
算法描述：
- 比较相邻的元素：如果第一个比第二个大，就交换它们两个；
- 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对，这样在最后的元素应该会是最大的数；
- 针对所有的元素重复以上的步骤，除了最后一个；
重复步骤1~3，直到排序完成。
排序方式：in-place
时间复杂度：
- 最佳情况：T(n) = O(n)
- 最差情况：T(n) = O(n2)
- 平均情况：T(n) = O(n2)
空间复杂度：O(1)
代码实现：
/*******bubble Sort algorithm **************/
public void bubble(int[] arr){//冒泡排序
for(int i = 0;i<arr.length;i++){
for(int j = 0;j<arr.length-1-i;j++){
if(arr[j] > arr[j+1]){
int temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
}
}
}
}
选择排序算法：
算法描述：
n个记录的直接选择排序可经过n-1趟直接选择排序得到有序结果。
初始状态：无序区为R[1…n]，有序区为空；
第i趟排序(i=1,2,3…n-1)开始时，当前有序区和无序区分别为R[1…i-1]和R(i…n）。该趟排序从当前无序区中-选出关键字最小的记录R[k]，将它与无序区的第1个记录R交换，使R[1…i]和R[i+1…n)分别变为记录个数增加1个的新有序区和记录个数减少1个的新无序区；
n-1趟结束，数组有序化了。
排序方式：in-place
时间复杂度：
- 最佳情况：T(n) = O(n2)
- 最差情况：T(n) = O(n2)
- 平均情况：T(n) = O(n2)
空间复杂度：O(1)
代码描述：
/*******Select Sort algorithm **************/
public void select(int[] arr){//选择排序
for(int i=0;i<arr.length;i++){
int min = arr[i];
int pos = -1;
boolean exc = false;//用来记录最小值是否改变过，如果没有改变，则后面就不需要交换
//其实也没有必要设置exc变量来记录，可以使用pos的值来判定，如果没有交换过，那么pos的值为-1；
for(int j = i;j<arr.length;j++){
if(min>arr[j]){
min = arr[j];
pos = j;
exc = true;
}
}
if(exc){
int temp = arr[i];
arr[i] = arr[pos];
arr[pos] = temp;
}
}
}
插入排序算法:
算法描述：
- 从第一个元素开始，该元素可以认为已经被排序；
- 取出下一个元素，在已经排序的元素序列中从后向前扫描；
- 如果该元素（已排序）大于新元素，将该元素移到下一位置；
- 重复步骤3，直到找到已排序的元素小于或者等于新元素的位置；
- 将新元素插入到该位置；
重复步骤2~5。
排序方式：in-place
时间复杂度：
- 最佳情况：T(n) = O(n)
- 最坏情况：T(n) = O(n2)
- 平均情况：T(n) = O(n2)
额外空间复杂度：O(1)
代码实现：
/*******Insert Sort algorithm **************/
public void insert(int[] arr){//直接插入排序
for(int i=1;i<arr.length;i++) {//从第二个元素开始
//pVal 用来记录当前元素的值，因为在移动元素时，会把当前元素的值给覆盖掉。
int pVal = arr[i];
int j = i-1;
while(pVal < arr[j]) {//后移元素
arr[j+1] = arr[j];
j--;
}
arr[j+1] = pVal;//找到合适位置后把当前元素插入到合适位置
}
}
希尔排序
算法描述：
希尔排序的基本步骤：
选择增量 ：gap=length/2，缩小增量：gap = gap/2
增量序列：用序列表示增量选择，{n/2, (n/2)/2, …, 1}
希尔排序的增量序列的选择与证明是个数学难题，我们选择的这个增量序列是比较常用的，也是希尔建议的增量，称为希尔增量，但其实这个增量序列不是最优的。此处我们做示例使用希尔增量。
先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，具体算法描述：
选择一个增量序列t1，t2，…，tk，其中ti>tj，tk=1；
按增量序列个数k，对序列进行k趟排序；
每趟排序，根据对应的增量ti，将待排序列分割成若干长度为m 的子序列，分别对各子表进行直接插入排序;
仅增量因子为1 时，整个序列作为一个表来处理，表长度即为整个序列的长度。
排序方式：in-place
时间复杂度：
- 最佳情况：T(n) = O(n)
- 最坏情况：T(n) = O(n2)
- 平均情况：T(n) =O(n1.3)
空间复杂度：O(1)
代码实现：
/*******Shell Sort algorithm **************/
public void shell(int[] arr) {
int gap = 1;//定义步长
while(gap<arr.length/3)//动态计算步长
gap=gap*3+1;
for(;gap>0;gap=(int)Math.floor(gap/3)) {
for(int i = gap;i<arr.length;i++) {
int temp = arr[i];
int j = i-gap;
//直接插入排序
for(;j>0 && arr[j]>temp;j-=gap) {
arr[j+gap] = arr[j];
}
arr[j+gap] = temp;
}
}
}
归并排序：
把长度为n的输入序列分成两个长度为n/2的子序列；
对这两个子序列分别采用归并排序；
将两个排序好的子序列合并成一个最终的排序序列。
排序方式：out-place
时间复杂度：
- 最佳情况：T(n) = O(nlog n)
- 最差情况：T(n) = O(nlog n)
- 平均情况：T(n) = O(nlog n)
空间复杂度：O(n)
代码描述：
/*******Merge Sort algorithm **************/
//先实现把两个有序数组合并成一个有序数组的函数
public int[] merge(int[] l,int[] r) {
int[] res=new int[l.length+r.length];
int i=0,j=0,k=0;
while(i<l.length && j<r.length) {
if(l[i]<r[j]) {
res[k++]=l[i++];
}else {
res[k++]=r[j++];
}
}
while(i<l.length)
res[k++]=l[i++];
while(j<r.length)
res[k++]=r[j++];
return res;
}
//下面来写归并排序，利用递归
public int[] mergeSort(int[] arr) {
if(arr.length < 2)//定义递归出口
return arr;
int mid = (int)Math.floor(arr.length/2);
int[] l = new int[mid];
int[] r = new int[arr.length-mid];
int lk = 0;
int rk = 0;
for(int i=0;i<mid;i++) {
l[lk++] = arr[i];
}
for(int i=mid;i<arr.length;i++) {
r[rk++] = arr[i];
}
return merge(mergeSort(l),mergeSort(r));
}
快速排序算法:
算法描述：
快速排序使用分治法来把一个串（list）分为两个子串（sub-lists）。
- 从数列中挑出一个元素，称为 “基准”（pivot），即枢纽元；
- 重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边），在这个分区退出之后，该基准就处于数列的中间位置，称为分区（partition）操作；
- 递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序。
排序方式：in-place
时间复杂度：
最佳情况：T(n) = O(nlog n)
最差情况：T(n) = O(n2)
平均情况：T(n) = O(nlog n)
空间复杂度：
平均：O(log n)
最差： O(n)
代码实现:
/***********Quick Sort*********************/
public void quickSort(int[] arr,int l,int r) {
if(l>=r) return;//设置递归出口
int pivot = arr[l];//设置标准枢轴量
int low = l;
int high = r;
while(low<high) {
while(low<high && arr[high]>pivot) high-=1;
arr[low] = arr[high];
while(low<high && arr[low]<=pivot) low+=1;
arr[high] = arr[low];
}
arr[low] = pivot;
quickSort(arr, l, low-1);
quickSort(arr, low+1, r);
}
以上经典排序算法的总结:
| 算法名称 | 平均时间复杂度 | 最好情况 | 最坏情况 | 空间复杂度 | 排序方式 | 稳定性 |
|---|---|---|---|---|---|---|
| 冒泡排序 | O(n^2) | O(n) | O(n^2) | O(1) | IN | Y |
| 选择排序 | O(n^2) | O(n^2) | O(n^2) | O(1) | IN | N |
| 插入排序 | O(n^2) | O(n^2) | O(n^2) | O(1) | IN | Y |
| Shell 排序 | O(nlogn) | O(n(logn)^2) | O(n(logn)^2) | O(1) | IN | N |
| 归并排序 | O(nlogn) | O(nlogn) | O(nlogn) | O(n) | OUT | Y |
| 快排 | O(nlogn) | O(nlogn) | O(n^2) | O(logn) | IN | N |