经典排序算法回顾
2017-04-14 本文已影响50人
昵称真难选
原文出自王艳涛的专栏转载请注明出处！
一、选择排序（最简单的排序算法）
思想：
- 找到数组中最小的元素，将他与数组的第一个元素交换位置（如果第一个元素就是最小元素就和自己交换）；
- 在剩下的元素中找到最小元素，将他与数组的第二个元素交换位置。
- 依次重复，直到整个数组有序。
private static void selectSort(int [] a){
int N = a.length;
for (int i = 0; i < N; i++ ) {
int min =i;
for(int j = i+1; j < N; j++){
if (a[j] < a[min]){
min = j;
}
}
int temp = a[i];
a[i] = a[min];
a[min] = temp;
}
}
特点：
- 当前索引左边元素都是有序的
- 对于长队为N的数组，大约需要N次交换、(N平方)/2次比较；
- 运行时间和输入无关
- 数据移动是最少的
二、插入排序
思想：顺序地将未排序元素取出，插入到已排序的地元素中。
private static void insertSort(int [] a){
int N = a.length;
for(int i = 1; i < N; i++){
for(int j = i; j > 0 && a[j] < a[j-1]; j--){
int temp = a[j];
a[j] = a[j-1];
a[j-1] = temp;
}
}
}
特点：
- 当前索引左边元素都是有序的；
- 排序所需时间取决于输入时的初始顺序，对部分有序或者接近有序的数组排序较快；
- 对于长度为N的不存在重复元素的数组，平均情况下比较（N平方）/4次、交换（N平方）/4，最坏情况下比较（N平方）/2次、交换（N平方）/2次，最好情况下，比较N-1次，交换0次。
改进思想：内循环中较大的元素向右移动，不用每次都交换两个元素，可以减少访问数组的次数。
private static void insertSort2(int [] a){
int N = a.length;
for(int i = 1; i < N; i++){
int temp = a[i];
int j;
for(j = i; j > 0 && temp < a[j-1]; j--){
a[j] = a[j-1];
}
a[j] = temp;
}
}
三、希尔排序
思想：构建h有序数组，在插入排序的基础上加入一个外循环将h按照递增序列递减，当h为1时，数组将排序完毕。
private static void shellSort(int [] a){
int N = a.length;
int h = 1;
while(h < N/3){
h = h*3 + 1;
}
while(h >= 1){
for(int i = h ; i < N; i++){
int temp = a[i];
int j;
for(j = i; j >= h && temp < a[j-h]; j -= h){
a[j] = a[j-h];
}
a[j] = temp;
}
h = h/3;
}
}
特点：
- 对于大规模数组排序适用
- 排序耗时不到平方级别，比较次数与N的二分之三次方成正比。
四、归并排序
思想：递归的将数组分成两半分别排序，然后将结果归并起来。
0.归并方法：
private static int []aux;
public static void main (String[] args) throws java.lang.Exception
{
int [] a ={3,5,6,8,9,0,1,2,4,7};//前五个元素有序，后五个元素有序
aux = new int[a.length];
merge(a, 0, 4,9);
}
private static void merge(int [] a, int lo, int mid, int hi){
int i = lo, j = mid+1;
for(int k = lo; k <=hi; k++){
aux[k] = a[k];//aux为外部定义的辅助数组，大小和数组a相同
}
for(int k = lo; k <= hi; k++){
if(i > mid) a[k] = aux[j++];
else if (j > hi) a[k] = aux[i++];
else if (aux[j] < aux[i]) a[k] = aux[j++];
else a[k] = aux[i++];
}
}
1.自顶向下的归并排序：
private static void mergeSort(int []a, int lo, int hi){
if(hi <= lo) return;
int mid = lo + (hi - lo)/2;
mergeSort(a, lo, mid);
mergeSort(a, mid+1, hi);
merge(a, lo, mid, hi);//代码见“0.归并方法”中的merge方法
}
特点：
- 对于超大规模数组排序适用；
- 对于长度为N的任意数组，比较次数为（1/2）NlgN至NlgN之间，访问数组的次数最多为6NlgN；
- 缺点：辅助数组使用的额外空间和N的大小成正比。
改进1：
由于递归回事小规模问题中的方法调用过于频繁，所以对小规模数组使用插入排序的方式，可以降低排序耗时。
private static void mergeSort2(int []a, int lo, int hi){
if(hi <= lo) return;
int mid = lo + (hi - lo)/2;
if((hi - lo)/2 <=3){//当数组长度不大于3时，启用插入排序。
insertSort3(a, lo, lo+mid);
insertSort3(a, lo+mid+1, hi);
}else{
mergeSort(a, lo, mid);
mergeSort(a, mid+1, hi);
}
merge(a, lo, mid, hi);
}
private static void insertSort3(int [] a, int lo, int hi){
int N = hi - lo;
for(int i = 1; i <= N; i++){
int temp = a[lo + i];
int j;
for(j = lo + i; j > 0 && temp < a[j-1]; j--){
a[j] = a[j-1];
}
a[j] = temp;
}
}
改进2：
如果a[mid]<a[mid+1]，说明数组已经有序，可以跳过归并方法，减少耗时。
private static void mergeSort3(int []a, int lo, int hi){
if(hi <= lo) return;
int mid = lo + (hi - lo)/2;
if((hi - lo)/2 <=2){
insertSort3(a, lo, lo+mid);
insertSort3(a, lo+mid+1, hi);
}else{
mergeSort(a, lo, mid);
mergeSort(a, mid+1, hi);
}
if(a[mid] <= a[mid+1]) return;//数组已有序，跳过merge方法
merge(a, lo, mid, hi);
}
改进3：
通过merge方法中交换a与aux的角色，省去for循环复制a到aux，节省耗时。
private static int []aux;
public static void main (String[] args) throws java.lang.Exception
{
int [] a ={3,2,6,1,4,9,0,5,7,8};
aux = new int[a.length];
mergeSort4(a, 0, 9);
a = aux;
}
private static void mergeSort4(int []a, int lo, int hi){
if(hi <= lo) return;
int mid = lo + (hi - lo)/2;
if((hi - lo)/2 <=2){
insertSort3(a, lo, lo+mid);
insertSort3(a, lo+mid+1, hi);
}else{
mergeSort(a, lo, mid);
mergeSort(a, mid+1, hi);
}
if(a[mid] <= a[mid+1]) return;//数组已有序，跳过merge方法
merge2(a, lo, mid, hi);
}
private static void merge2(int [] a, int lo, int mid, int hi){
int i = lo, j = mid+1;
for(int k = lo; k <= hi; k++){
//交换a与aux角色
if(i > mid) aux[k] = a[j++];
else if (j > hi) aux[k] = a[i++];
else if (a[j] < a[i]) aux[k] = a[j++];
else aux[k] = a[i++];
}
}
2.自底向上的归并排序：
private static void mergeSortBU(int []a){
int N = a.length;
for(int sz = 1; sz < N; sz =sz +sz){
for (int lo = 0; lo < N - sz; lo += sz +sz) {
merge(a, lo, lo+sz-1, Math.min(lo + sz +sz-1, N-1));
}
}
}
五、快速排序
思想：递归的切分数组，使切分点左边都小于切分点元素，切分点右边都大于切分点元素，最终整个数组有序。
切分后的数组具有三个特点：
- 对于切分点j，a[j]元素位置已经排定
- a[lo]到a[j-1]的元素都小于a[j]
- a[j+1]到a[hi]的元素都大于a[j]
0.切分方法：
private static int partition(int []a, int lo, int hi){
int i = lo, j= hi+1;
int v = a[lo];
while(true){
while(a[++i] < v) if(i == hi) break;
while(v < a[--j]) if(j == lo) break;
if( i >= j) break;
int temp = a[j];
a[j] = a[i];
a[i] = temp;
}
int temp = a[j];
a[j] = a[lo];
a[lo] = temp;
return j;
}
1.快速排序：
private static void quickSort(int []a, int lo, int hi){
if (hi <= lo) return;
int j = partition(a, lo, hi);
quickSort(a, lo, j-1);
quickSort(a, j+1, hi);
}
特点：
- 平均需要大约2NlnN次比较，最坏需要NN/2次比较，但是随即打乱数组可以避免最坏情况的出现。
改进：
由于递归回事小规模问题中的方法调用过于频繁，况且对小规模数组使用插入排序的方式更快。
一般情况下，小数组的长度定义在5-15之间效果较好
private static void quickSort2(int []a, int lo, int hi){
if (hi <= lo + 3){//数组长度不大于3（最好5-15）时，使用插入排序
insertSort3(a, lo, hi);
return;
}
int j = partition(a, lo, hi);
quickSort2(a, lo, j-1);
quickSort2(a, j+1, hi);
}
2.三向切分快速排序：
思想：从左到右遍历数组，维护一个指针lt使a[lo...lt-1]都小于v，一个指针gt使a[gt+1...hi]都大于v，一个指针i使a[lt...i-1]都等于v，a[i...gt]尚未确定。
private static void quickSort3(int []a, int lo, int hi){
if(hi <= lo) return;
int lt = lo, i = lo+1, gt =hi;
int v = a[lo];
while(i <= gt){
if(a[i] < v){
int temp = a[lt];
a[lt] = a[i];
a[i] = temp;
lt++;
i++;
}else if (a[i] > v) {
int temp = a[gt];
a[gt] = a[i];
a[i] = temp;
gt--;
}else{
i++;
}
}
quickSort3(a, lo, lt-1);
quickSort3(a, gt+1, hi);
}
