常使用的排序方法总结
数据结构中常用的排序方法主要有以下几种:
冒泡排序
快速排序
希尔排序
堆排序
直接选择排序
直接插入排序
归并排序
下面分别对其介绍,总体可以分为三类:
排序LowB三人组:冒泡排序,选择排序,插入排序
排序NB三人组:快速排序,堆排序,归并排序
其他排序:希尔排序,计数排序,归并排序
0、引子 这里给出了七种排序算法,根据清华大佬的总结分类可以大致分为三类
1、冒泡排序 冒泡排序是接触排序算法以来最经常使用的排序算法,两两比较相邻数据,如果反序则交换,直到没有反序记录为止。外层循环一次会将最大的值移到最右边,二次将次大值移到最右边。
a.程序 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 void BobuleSort (vector <int > &array ) { for (int i = 0 ; i < array .size() - 1 ; i++) { for (int j = 0 ; j < array .size() - 1 - i; j++) { if (array [j+1 ] < array [j]) { int temp = array [j+1 ]; array [j+1 ] = array [j]; array [j] = temp; } } } }
b.复杂度分析 冒泡排序的时间复杂度最简单的情况是原本就是一个递增的数组,比较(n-1)次。最复杂的情况为逆序数组,比较次数为1+2+…+(n-1)+n次,所以时间复杂度为n*(n-1)/2。
c.冒泡排序的算法改进 冒泡排序存在某一趟遍历过程中并没有发生任何交换的情况,这时可以在每一趟开始前先定义一个状态exchange为false,如果在一趟中存在交换,则将exchange改为true。
然后在每一趟结束后就可以进行判断exchange,如果还是为false就说明以已经有序,可以结束了。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 void BobuleSort (vector <int > &array ) { for (int i = 0 ; i < array .size() - 1 ; i++) { bool exchange=false ; for (int j = 0 ; j < array .size() - 1 - i; j++) { if (array [j+1 ] < array [j]) { exchange=true ; int temp = array [j+1 ]; array [j+1 ] = array [j]; array [j] = temp; } } if (!exchange) break ; } }
2、快速排序 快速排序最核心的地方在于找到中轴值,小于中轴在左边,大于中轴在右边,右左交替判断,满足继续移动,不满足换左右,排完然后递归进行。快速排序使用到了递归的思想。
a.程序 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 void Quick_Sort (vector <int > &Array, int L, int R) { if (L >= R) return ; int left = L, right = R; int pivot = Array[left]; while (left < right) { while (left < right&&Array[right]>=pivot) { right--; } if (left < right) { Array[left] = Array[right]; } while (left < right && Array[left] <= pivot) { left++; } if (left < right) { Array[right] = Array[left]; } if (left >= right) { Array[left] = pivot; } Quick_Sort(Array, L, right - 1 ); Quick_Sort(Array, right + 1 , R); } }
上面的代码不够直观,我自己又写了一个更加直观的方法,主要是利用partition函数来找到中间的那个可以分割左右的下标。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 #include <iostream> #include <vector> using namespace std ;void Print (vector <int >& nums) { for (auto c:nums) cout <<c<<" " ; cout <<endl ; } int partition (vector <int >& nums,int left,int right) { int mid=nums[left]; while (left<right){ while (left<right&&nums[right]>=mid) right--; if (left<right) nums[left]=nums[right]; while (left<right&&nums[left]<=mid) left++; if (left<right) nums[right]=nums[left]; } nums[left]=mid; return left; } void QuickSort (vector <int >& nums,int L,int R) { if (L<R) { int pivot=partition(nums,L,R); QuickSort(nums,L,pivot-1 ); QuickSort(nums,pivot+1 ,R); } } int main () { vector <int > nums; nums.push_back(12 ); nums.push_back(4 ); nums.push_back(8 ); nums.push_back(6 ); nums.push_back(9 ); nums.push_back(0 ); int len=nums.size(); QuickSort(nums,0 ,len-1 ); Print(nums); system("pause" ); }
b.复杂度分析 快速排序的时间复杂度为nlongn,空间复杂度的话,主要是递归造成的栈空间的使用,最好的情况递归深度为log2N其空间复杂度为logn
3、希尔排序 1、分组
找到一定的间隔,每个间隔内N个元素为一组,然后对每一个子序列进行直接插排序。
希尔排序和直接插入排序关系密不可分。
2、每一组的组内进行排序
组内排好序后,重新设定一个间隔,重新设的间隔为第一次分组的一半。下一次在进行减小一般,直至最后为1。
4、堆排序 堆的概念 :堆是数据结构中二叉树的一种类型,一种特殊的二叉树。根节点(亦称为堆顶)的关键字是堆里所有节点关键字中最大者,称之为大根堆,大根堆要求根节点的关键字即大于等于左子树的关键字值又大于等于右子树的关键字值。
堆的向下调整性质 :假设根节点的左右子树都是堆,但根节点不满足堆的性质,可通过一次向下调整将其变成一个堆。
堆的调整与构造 :农村包围城市,先从最后一个非叶子节点进行二叉树的考虑。
堆排序过程 :堆排序的优质文章
构造一个大顶堆,取堆顶数字(也就是最大值)
再将剩下的数字构造一个大顶堆,取堆顶数字(也就是剩下所有元素的最大值)
重复以上操作,直到取完堆中的数字,最终得到一个从大到小的排序序列
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 package sortdemo;import java.util.Arrays;public class HeapSort { public static void main (String []args) { int []arr = {9 ,8 ,7 ,6 ,5 ,4 ,3 ,2 ,1 }; sort(arr); System.out.println(Arrays.toString(arr)); } public static void sort (int []arr) { for (int i=arr.length/2 -1 ;i>=0 ;i--){ adjustHeap(arr,i,arr.length); } for (int j=arr.length-1 ;j>0 ;j--){ swap(arr,0 ,j); adjustHeap(arr,0 ,j); } } public static void adjustHeap (int []arr,int i,int length) { int temp = arr[i]; for (int k=i*2 +1 ;k<length;k=k*2 +1 ){ if (k+1 <length && arr[k]<arr[k+1 ]){ k++; } if (arr[k] >temp){ arr[i] = arr[k]; i = k; }else { break ; } } arr[i] = temp; } public static void swap (int []arr,int a ,int b) { int temp=arr[a]; arr[a] = arr[b]; arr[b] = temp; } }
堆排序 的平均复杂度:O(N*logN)
5、直接选择排序 a.直接插入排序思想 主要思想为,对于一个乱序数组,我们首先从全部里面找到一个最小的放在最前面,然后从剩下的里面找到一个最小的再放到次前面,最后得到一个有序的数组。
从下标零开始,同时需要记忆min_i和min_value。
如果发现后面的值小于当前,则就需要交换。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 void Select_sort (vector <int > nums,int len) { int i,j; int min_value,min_pos; for (i=0 ;i<len-1 ;i++) {。 min_pos=i; for (j=i+1 ;j<len;j++) { if (nums[j]<min_value) min_pos=j; } int temp=nums[i]; nums[i]=nums[min_pos]; nums[min_pos]=temp; } }
b.时间复杂度分析 这个算法的复杂度显而易见,时间复杂度为O(n^2);
6、直接插入排序 a.插入排序思路 直接插入排序就是我们经常玩扑克牌时多用的方法,每一次我们都认为我们当前的排序是有序的,然后下一个元素进来时,我们通过插入排序将其放入指定的位置,当最后一个元素放完时,插入排序也就结束了。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 void insert_sort (vector <int >& a,int len) { int value; for (int i=1 ;i<len;i++) { int temp=nums[i]; int j=i-1 ; while (j>=0 &&nums[j]>temp) { nums[j+1 ]=nums[j]; j--; } nums[j+1 ]=temp; } }
b. 时间复杂度分析 由于也是两个层大的循环,所以插入排序的时间复杂度为O(n^2)。
7、归并排序
将待排序序列中的数字分为若干组,每个数字为一组
将若干组两两合并,保证合并后的数组是有序的
重复进行第二步,最终得到排序后的一组