以下我说的排序算法都是说的从小到大排序
1. 插入排序
- insertSort(int a[]){
- int length = a.length;
- int b[] = new int [length+1];
- for (int i=0;i<a.length;i++) { // 复制数组, 将下标为 0 的空出来作为哨兵
- b[i+1] = a[i];
- }
- for (int i=1;i<b.length;i++){ // 找 n 次, 每次找一个数
- b[0] = b[i];
- for (int j=i;j>0;j--){
- if (b[j]<b[j-1]){
- int x = b[j];
- b[j] = b[j-1];
- b[j-1] =x;
- }else{
- break;
- }
- }
- }
- }
插入排序是每次都确定一个数, 在最差情况下, 每次都需要遍历当前插入元素的前面所有元素, 所以其时间复杂度为 O(N^2), 有一个哨兵位置, 所以空间复杂度为 O(1), 插入排序是稳定的排序算法
2. 冒泡排序
- BubbleSort(int a[]){
- for (int i=0;i<a.length-1;i++){ // 一共需要比较 n-1 次
- for (int j=0;j<a.length-1-i;j++){ // 每次需要比较到什么地方停止
- if (a[j]>a[j+1]){
- int x = a[j];
- a[j]=a[j+1];
- a[j+1]=x;
- }
- }
- }
- }
冒泡排序是每次都是从前到后的扫描, 每次都把最大的元素放在最后, 所以时间复杂度是 O(n^2), 每次需要一个变量保存中间值, 所以空间复杂度为 O(1), 冒泡排序算法是稳定的排序算法
3. 快速排序
- QuickSort(int a[],int low,int high){
- if (low<high){
- int part = Partition(a,low,high);
- QuickSort(a,low,part-1);
- QuickSort(a,part+1,high);
- }
- }
- int Partition(int a[], int low,int high){
- int value = a[low]; // 以 low 为中间值
- while(low<high){
- while(low<high && a[high]>=value)
- high--;
- a[low] = a[high];
- while(low<high && a[low]<=value)
- low++;
- a[high]=a[low];
- }
- a[low]=value;
- return low;
- }
快速排序是不稳定的排序算法, 它的时间复杂度是 O(nlogn), 但是在最坏情况下可以达到 O(n^2), 为什么是 nlogn 呢?
因为快速排序每次划分中间点后, 都会遍历一遍所有元素, 然后将小的值放在中间元素的左边, 把大的元素放在中间值的右边, 所以一趟的
时间复杂度时 n, 而且如果每次划分的足够好的话, 会形成类似于二叉树的情况, 能在树的深度为 logn 时完成划分, 所以时间复杂度为 O(nlogn)
在最坏的情况下, 会发生划分的倾斜, 导致树的深度为 n, 最终的时间复杂度为 O(n^2)
那么怎么避免或者优化呢?
可以采用三数取中或者随机选取中间元素的办法, 也可以在划分的时候, 将和中间元素相等的元素放在中间元素的周围, 另外, 对于划分到一定
小长度的元素, 可以采取插入排序, 也可以提升效率
4. 堆排序 (要做大顶堆, 才能完成从小到大的排序)
- HeapSort(int a[]){ // 从下标 1 开始放数据
- for (int i=(a.length-1)/2;i>=1;i--){
- HeapAdjust(a,i,a.length-1); // 先构建大顶堆
- }
- for (int i=0;i<a.length-1;i++){ // 因为 a[0] 没放元素, 所以只有 a.length-1 个需要调整
- int x = a[0];
- a[0]=a[a.length-1-i];
- a[a.length-1-i]=x;
- HeapAdjust(a,1,a.length-2-i);
- }
- }
- HeapAdjust(int a[],int s,int m){ //s 代表开始调整的元素, m 代表数组的最大下标
- int x= a[s]; // 记录要调整的值
- for (int i=s*2;i<=m;i++){
- if (i+1<=m &&a[i]<a[i+1]) // 有右孩子并且右孩子比较大
- i++;
- if (x>a[i]) // 父亲比较大, 不用调整
- break;
- a[s]=a[i];
- s=i;
- }
- a[s]=x; // 将父类调入该位置
- }
堆排序的时间复最好 / 最坏杂度均为 O(nlogn), 且是不稳定的排序算法
原因: 堆排序的抽象是严格的完全二叉树, 所以每次输出最大元素后, 需要调整, 调整时比较的树的最大深度为 logn, 而且每次只调整出一个最大的元素, 完成所有排序一共需要调整 n 次, 所以时间复杂度为 O(nlogn), 另外, 堆排序不适合排序元素太少的情况, 原因在于虽然堆排序在排序时很快, 但在创建初始堆时需要一定的时间复杂度
5. 归并排序
- MergeSort(int a[]){
- int b = new int [a.length+1];
- sort(a,0,a.length-1,b);
- }
- sort(int a[],int left, int right,int b[]){ //b 用作辅助空间
- if(left<right){
- int mid = (left+right)/2;
- sort(a,left,mid,b);
- sort(a,mid+1,right,b);
- merge(a,left,mid,right,b);
- }
- merge(int a[],int left,int mid,int right, int b[]){
- int i=left;
- int j=mid+1;
- int index=0;
- while(i<=mid &&j<=right){
- if (a[i]<a[j])
- b[index++]=a[i++];
- else
- b[index++]=a[j++];
- }
- while(i<=mid)
- b[index++]=a[i++]
- while(j<=right)
- b[index++]=a[j++]
- index=0; // 将 b 中的数据还原到 a 中
- while(left<=right)
- a[left++]=b[index++]
- }
归并排序的的时间复杂度时 O(nlogn), 空间复杂度是 O(n), 并且他是稳定的排序算法
时间复杂度原因: 归并排序和堆排序有相似之处, 都是使用分治法的思想, 而且都是严格的完全二叉树, 所以深度为 logn, 在每一层合并的时候, 都是遍历了数组, 所以时间复杂度为 O(nlogn)
来源: https://www.cnblogs.com/by-my-blog/p/10801704.html