解析常用排序算法

Java基础

浏览数:85

2019-9-17

AD:资源代下载服务

以下我说的排序算法都是说的从小到大排序

1.插入排序

 1 insertSort(int a[]){
 2     int length = a.length;
 3     int b[] = new int [length+1];
 4     for (int i=0;i<a.length;i++) {      //复制数组,将下标为0的空出来作为哨兵
 5          b[i+1] = a[i];
 6     }
 7     for (int i=1;i<b.length;i++){     //找n次,每次找一个数
 8          b[0] = b[i];
 9         for (int j=i;j>0;j--){
10             if (b[j]<b[j-1]){
11                 int x = b[j];
12                 b[j] = b[j-1];
13                 b[j-1] =x;
14             }else{
15                 break;
16             }
17         }
18     }
19     
20 }

插入排序是每次都确定一个数,在最差情况下,每次都需要遍历当前插入元素的前面所有元素,所以其时间复杂度为O(N^2),有一个哨兵位置,所以空间复杂度为O(1),插入排序是稳定的排序算法

2.冒泡排序

 1 BubbleSort(int a[]){
 2     for (int i=0;i<a.length-1;i++){   //一共需要比较n-1次
 3         for (int j=0;j<a.length-1-i;j++){   //每次需要比较到什么地方停止
 4             if (a[j]>a[j+1]){
 5                 int x = a[j];
 6                 a[j]=a[j+1];
 7                 a[j+1]=x;
 8             }
 9         }
10     }
11 }

冒泡排序是每次都是从前到后的扫描,每次都把最大的元素放在最后,所以时间复杂度是O(n^2),每次需要一个变量保存中间值,所以空间复杂度为O(1),冒泡排序算法是稳定的排序算法

3.快速排序

 1 QuickSort(int a[],int low,int high){
 2     if (low<high){
 3         int part = Partition(a,low,high);
 4         QuickSort(a,low,part-1);
 5         QuickSort(a,part+1,high);
 6     }
 7     
 8 }
 9 int Partition(int a[], int low,int high){
10     int value = a[low];    //以low为中间值
11     while(low<high){
12         while(low<high && a[high]>=value)
13             high--;
14         a[low] = a[high];
15         while(low<high && a[low]<=value)
16             low++;
17         a[high]=a[low];
18     }
19     a[low]=value;
20     return low;
21 }

快速排序是不稳定的排序算法,它的时间复杂度是O(nlogn),但是在最坏情况下可以达到O(n^2),为什么是nlogn呢?

因为快速排序每次划分中间点后,都会遍历一遍所有元素,然后将小的值放在中间元素的左边,把大的元素放在中间值的右边,所以一趟的

时间复杂度时n,而且如果每次划分的足够好的话,会形成类似于二叉树的情况,能在树的深度为logn时完成划分,所以时间复杂度为O(nlogn)

在最坏的情况下,会发生划分的倾斜,导致树的深度为n,最终的时间复杂度为O(n^2)

那么怎么避免或者优化呢?

可以采用三数取中或者随机选取中间元素的办法,也可以在划分的时候,将和中间元素相等的元素放在中间元素的周围,另外,对于划分到一定

小长度的元素,可以采取插入排序,也可以提升效率

4.堆排序(要做大顶堆,才能完成从小到大的排序)

 1 HeapSort(int a[]){     //从下标1开始放数据
 2     
 3     for (int i=(a.length-1)/2;i>=1;i--){
 4         HeapAdjust(a,i,a.length-1);         //先构建大顶堆
 5     }
 6     for (int i=0;i<a.length-1;i++){     //因为a[0]没放元素,所以只有a.length-1个需要调整
 7         int x = a[0];
 8         a[0]=a[a.length-1-i];
 9         a[a.length-1-i]=x;
10         HeapAdjust(a,1,a.length-2-i);
11     }
12 }
13 HeapAdjust(int a[],int s,int m){    //s代表开始调整的元素,m代表数组的最大下标
14     int x= a[s];   //记录要调整的值 
15     for (int i=s*2;i<=m;i++){
16         if (i+1<=m &&a[i]<a[i+1])   //有右孩子并且右孩子比较大
17             i++;
18         if (x>a[i])     //父亲比较大,不用调整
19             break;
20         a[s]=a[i];
21         s=i;
22     }
23     a[s]=x;     //将父类调入该位置
24 }

堆排序的时间复最好/最坏杂度均为O(nlogn),且是不稳定的排序算法

原因:堆排序的抽象是严格的完全二叉树,所以每次输出最大元素后,需要调整,调整时比较的树的最大深度为logn,而且每次只调整出一个最大的元素,完成所有排序一共需要调整n次,所以时间复杂度为O(nlogn),另外,堆排序不适合排序元素太少的情况,原因在于虽然堆排序在排序时很快,但在创建初始堆时需要一定的时间复杂度

5.归并排序

 1 MergeSort(int a[]){
 2     int b = new int [a.length+1];
 3     sort(a,0,a.length-1,b);
 4 }
 5 sort(int a[],int left, int right,int b[]){    //b用作辅助空间
 6     if(left<right){
 7         int mid = (left+right)/2;
 8         sort(a,left,mid,b);
 9         sort(a,mid+1,right,b);
10         merge(a,left,mid,right,b);
11 }
12 merge(int a[],int left,int mid,int right, int b[]){
13     int i=left;
14     int j=mid+1;
15     int index=0;
16     while(i<=mid &&j<=right){
17         if (a[i]<a[j])
18             b[index++]=a[i++];
19         else
20             b[index++]=a[j++];
21     }
22     while(i<=mid)
23         b[index++]=a[i++]
24     while(j<=right)
25         b[index++]=a[j++]
26     index=0;      //将b中的数据还原到a中
27     while(left<=right)
28         a[left++]=b[index++]
29 }

归并排序的的时间复杂度时O(nlogn),空间复杂度是O(n),并且他是稳定的排序算法

时间复杂度原因:归并排序和堆排序有相似之处,都是使用分治法的思想,而且都是严格的完全二叉树,所以深度为logn,在每一层合并的时候,都是遍历了数组,所以时间复杂度为O(nlogn)

作者:流浪猿球