常见的五种排序算法
- 2019 年 12 月 26 日
- 筆記
冒泡排序
冒泡排序简介
冒泡排序只会操作相邻的两个数据。每次冒泡操作都会对相邻的两个元素进行比较，看是否满足大小关系要求。
如果不满足就让它俩互换。一次冒泡会让至少一个元素移动到它应该在的位置，重复 n 次，就完成了 n 个数据的排序工作。大的数往下沉，小的数往下冒。 稳定、原地排序，最好时间复杂度为O(n)，最坏与平均时间复杂度为O(n2)。
原地排序简介
原地排序指的是空间复杂度为O(1)的排序算法。
稳定排序简介
稳定性指的是：如果待排序列中存在值相等的元素，经过排序之后，相等元素的先后顺序没有改变 比如我们有一组数据 2，9，3，4，8，3，按照大小排序之后就是 2，3，3，4，8，9。 这组数据里有两个 3。经过某种排序算法排序之后，如果两个 3 的前后顺序没有改变，那我们就把这种排序算法叫作稳定的排序算法；如果前后顺序发生变化，那对应的排序算法就叫作不稳定的排序算法。
冒泡代码代码实现
public class BubbleSort { public static void main(String[] args) { // TODO Auto-generated method stub int[] data=new int[]{2,3,5,4,7,6,9,10,12,11,23,22,18,8}; bubbleSort(data); for(int i=0;i<data.length;i++){ System.out.print(data[i]+" "); } } public static void bubbleSort(int[] data){ if(data.length<=1) return; for(int i=0;i<data.length;i++){ //提前退出冒泡循环的标志位 boolean flag = false; for(int j=0;j<data.length-1-i;++j){ if(data[j]>data[j+1]){ int temp = data[j]; data[j] = data[j+1]; data[j+1] = temp; flag = true;//有数据交换 } } if(!flag) break;//没有数据交换，退出 } } }
插入排序
插入排序简介
我们将数组中的数据分为两个区间，已排序区间和未排序区间。初始已排序区间只有一个元素，就是数组的第一个元素。插入算法的核心思想是取未排序区间中的元素，在已排序区间中找到合适的插入位置将其插入，并保证已排序区间数据一直有序。重复这个过程，直到未排序区间中元素为空，算法结束。 稳定、原地排序，最好时间复杂度为O(n)，最坏与平均时间复杂度为O(n2)。
代码实现
public class InsertSort { public static void main(String[] args) { // TODO Auto-generated method stub int[] data=new int[]{4,3,2,1,5}; insertSort(data); for(int i=0;i<data.length;i++){ System.out.print(data[i]+" "); } } public static void insertSort(int[] data){ if(data.length<=1) return; for(int i=1;i<data.length;++i){ int value = data[i]; int j=i-1; for(;j>=0;--j){ if(data[j]>value){ data[j+1] = data[j]; }else { break; } } data[j+1]=value; } } }
选择排序
选择排序简介
选择排序算法的实现思路有点类似插入排序，也分已排序区间和未排序区间。但是选择排序每次会从未排序区间中找到最小的元素，将其放到已排序区间的末尾。 不稳定、原地排序，最好时间复杂度为O(n2)，最坏与平均时间复杂度为O(n2)。 选择排序是一种不稳定的排序算法。选择排序每次都要找剩余未排序元素中的最小值，并和前面的元素交换位置，这样破坏了稳定性。
代码实现
public class SelectSort { public static void main(String[] args) { // TODO Auto-generated method stub int[] data=new int[]{2,3,5,4,7,6,9,10,12,11,23,22,18,8}; selectSort(data); for(int i=0;i<data.length;i++){ System.out.print(data[i]+" "); } } public static void selectSort(int[] data){ if(data.length<=1) return; for(int i=0;i<data.length-1;++i){ int minIndex=i; for(int j=i+1;j<data.length;++j){ if(data[j]<data[minIndex]){ minIndex = j; } } int temp = data[i]; data[i] = data[minIndex]; data[minIndex] = temp; } } }
归并排序
归并排序简介
如果要排序一个数组，我们先把数组从中间分成前后两部分，然后对前后两部分分别排序，再将排好序的两部分合并在一起，这样整个数组就都有序了。 归并排序用的是一种分治思想，它不是原地排序，即空间复杂度不是O(1)，空间复杂度为O(n),不管最好还是最坏或平均，它的时间复杂度都为O(nlogn)，是一个稳定的算法。
代码实现
/** * 归并排序 * 将需要排序的数组从中间分成两部分，将这两部分分别排序，再将排序好的两部分合并在一起 * 时间复杂度O(nlogn) * 空间复杂度(n) * */ public class MergeSort { public static void main(String[] args) { int[] a= new int[]{1,2,4,3,45,34,23,6,7}; mergeSort(a, 9); for(int i=0;i<a.length;i++){ System.out.print(a[i]+" "); } } private static void mergeSort(int[] a,int n){ mergeIntaily(a, 0, n-1); } private static void mergeIntaily(int[] a,int p,int r){ if(p>=r) return; int q = p+(r-p)/2; mergeIntaily(a, p, q); mergeIntaily(a, q+1, r); merge(a, p, q, r); } private static void merge(int[] a,int p,int q,int r){ int i=p; int j = q+1; int k=0; //申请一个数组，大小与a[p..r]相同 int[] tmp = new int[r-p+1]; //用两个游标，一个i指向a[p..q]中的第一个元素,一个j指向a[q+1..r]的第一个元素, //如果a[i]<=a[j],就将a[i]的值放进tmp数组中,i后移,否则将a[j]元素放进tmp数组中,j后移 while(i<=q&&j<=r){ if(a[i]<=a[j]){ tmp[k++] = a[i++]; }else { tmp[k++] = a[j++]; } } //判断那部分数组剩余 int start = i; int end = q; if(j<=r){ start = j; end = r; } //将剩余数组放进tmp中 while(start<=end){ tmp[k++] = a[start++]; } //在将tmp数组中的元素放回原数组中 for(i=0;i<=r-p;i++){ a[p+i] = tmp[i]; } } }
merge(A[p…r], A[p…q], A[q+1…r]) 这个函数的作用就是，将已经有序的 A[p…q] 和 A[q+1…r] 合并成一个有序的数组，并且放入 A[p…r]。 申请一个临时数组 tmp，大小与 A[p…r] 相同。我们用两个游标 i 和 j，分别指向 A[p…q] 和 A[q+1…r] 的第一个元素。比较这两个元素 A[i] 和 A[j]，如果 A[i]<=A[j]，我们就把 A[i] 放入到临时数组 tmp，并且 i 后移一位，否则将 A[j] 放入到数组 tmp，j 后移一位。 继续上述比较过程，直到其中一个子数组中的所有数据都放入临时数组中，再把另一个数组中的数据依次加入到临时数组的末尾，这个时候，临时数组中存储的就是两个子数组合并之后的结果了。最后再把临时数组 tmp 中的数据拷贝到原数组 A[p…r] 中。
快速排序
快速排序简介
要排序的数组下标从p到r的一组数据，选取从p到r之间的任意一个数据作为pivot(分区点),也是分治思想。 快速排序是原地排序，不稳定，最坏时间复杂度为O(n2)，最好和平均时间复杂度都为O(nlogn)，空间复杂度为O(1)。
代码实现
public class QuickSort { public static void main(String[] args) { // TODO Auto-generated method stub int[] a= new int[]{1,2,4,3,45,34,23,6,7}; quickSort(a, 9); for(int i=0;i<a.length;i++){ System.out.print(a[i]+" "); } } private static void quickSort(int[] a,int n){ quickSortIntaily(a, 0, n-1); } private static void quickSortIntaily(int[] a,int p,int r){ if(p>=r) return; //递归终止条件 int q= partition(a, p, r); quickSortIntaily(a, p, q-1); quickSortIntaily(a, q+1, r); } //分区函数,随机选择一个元素作为pivot，一般选取从p到r的最后一个元素，然后对a[p..r]分区，返回pivot下标 private static int partition(int[] a,int p,int r){ int pivot = a[r]; int i=p; for(int j=p;j<r;++j){ if(a[j]<pivot){ int tmp = a[i]; a[i] = a[j]; a[j] = tmp; ++i; } } int tmp = a[i]; a[i] = a[r]; a[r] = tmp; return i; } }
遍历 p 到 r 之间的数据，将小于 pivot 的放到左边，将大于 pivot 的放到右边，将 pivot 放到中间。经过这一步骤之后，数组 p 到 r 之间的数据就被分成了三个部分，前面 p 到 q-1 之间都是小于 pivot 的，中间是 pivot，后面的 q+1 到 r 之间是大于 pivot 的。
归并与快排区别
- 归并排序的处理过程是由下到上的，先处理子问题，然后再合并。而快排处理过程是由上到下的，先分区，然后再处理子问题。归并排序虽然是稳定的、时间复杂度为 O(nlogn) 的排序算法，但是它是非原地排序算法；
- 归并排序和快速排序是两种稍微复杂的排序算法，都是使用分治的思想，代码都通过递归来实现，过程相似；
