排序

学习视频推荐
工具网站
notion image
 
代码设计原则
模板方法
public abstract class BaseSort { public abstract <E extends Comparable<E>> void sort(E[] a); public static <E> void swap(E[] a, int min, int i) { E temp = a[min]; a[min] = a[i]; a[i] = temp; } }
生成随机数组
public class ArrayGenerator { private ArrayGenerator() { } /** * 生成顺序数组 * * @param n:数组规模 * @return java.lang.Integer[] * @author wangjie * @date 2023/3/8 19:27 * @since 1.0.0 */ public static Integer[] generateOrderedArray(int n) { Integer[] arr = new Integer[n]; for (int i = 0; i < n; i++) { arr[i] = i; } return arr; } /** * 生成随机数组 * * @param n:数组规模 * @param bound:随机数字的范围 0 <= nextInt结果 < bound。 * @return java.lang.Integer[] * @author wangjie * @date 2023/3/8 19:27 * @since 1.0.0 */ public static Integer[] generateRandomArray(int n, int bound) { Integer[] arr = new Integer[n]; Random rnd = new Random(); for (int i = 0; i < n; i++) { arr[i] = rnd.nextInt(bound); } return arr; } }
 
package com.onethink.util; import com.onethink.sort.BaseSort; public class SortHelper { private SortHelper() { } /** * 判断是否顺序排序完成 * * @return boolean * @author wangjie * @date 2023/3/8 18:57 * @since 1.0.0 */ public static <E extends Comparable<E>> boolean isSorted(E[] arr) { boolean forwardFlag = true; for (int i = 0; i < arr.length - 1; i++) { if (arr[i].compareTo(arr[i + 1]) > 0) { forwardFlag = false; } } boolean reverseFlag = true; for (int i = arr.length - 1; i > 0; i--) { if (arr[i - 1].compareTo(arr[i]) < 0) { reverseFlag = false; } } return forwardFlag || reverseFlag; } /** * 判断是否顺序排序完成 * * @return boolean * @author wangjie * @date 2023/3/8 18:57 * @since 1.0.0 */ public static <E extends Comparable<E>> void sortTest(String sortName, E[] arr) { long startTime = System.nanoTime(); Object o = null; try { Class<?> clazz = Class.forName(sortName); BaseSort sortClas = (BaseSort) clazz.newInstance(); sortClas.sort(arr); } catch (Exception e) { throw new RuntimeException(e); } long endTime = System.nanoTime(); double time = (endTime - startTime) / 1000000000.0; if (!SortHelper.isSorted(arr)) { throw new RuntimeException(sortName + " failed"); } System.out.println(String.format("%s算法,数据规模n = %d , 耗时%f s", sortName, arr.length, time)); } }

冒泡排序

冒泡排序(Bubble Sort)是一种简单的排序算法。它重复地走访过要排序的数列,一次比较两个元素,如果它们的顺序错误就把它们交换过来。走访数列的工作是重复地进行直到没有再需要交换,也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。
 
排序前 : {21 ,4, 5, 6, 15, 3, 2, 1}
排序后 : {1, 2, 3, 4, 5, 6, 15, 21}
 

排序原理

  1. 比较相邻的元素。如果前一个元素比后一个元素大,就交换这两个元素的位置。
  1. 对每一对相邻元素做同样的工作,从开始第一对元素到结尾的最后一对元素。最终最后位置的元素就是最大值。
 
notion image
核心思路
假设数组长度为N
最细粒度的两两比较即为内层循环代码体.比较轮数为外层循环
总轮数=N-1,每轮参加比较的元素下标 0到 N-1 -轮数
 

API设计

notion image
 
public class Bubble { /* 对数组a中的元素进行升序排序 */ public static void sort(Comparable[] a){ for(int i=a.length-1;i>0;i--){ for(int j=0;j<i;j++){ //比较索引j和索引j+1处的值 if (greater(a[j],a[j+1])){ exch(a,j,j+1); } } } } /* 比较v元素是否大于w元素 */ private static boolean greater(Comparable v,Comparable w){ return v.compareTo(w)>0; } /* 数组元素i和j交换位置 */ private static void exch(Comparable[] a,int i,int j){ Comparable temp; temp = a[i]; a[i]=a[j]; a[j]=temp; } }
public class BubbleTest { public static void main(String[] args) { Integer[] arr = {21,4,5,6,15,3,2,1}; Bubble.sort(arr); System.out.println(Arrays.toString(arr));//[1, 2, 3, 4, 5, 6, 15, 21] } }
复杂度分析
冒泡排序使用了双层for循环,其中内层循环的循环体是真正完成排序的代码,所以,我们分析冒泡排序的时间复杂度,主要分析一下内层循环体的执行次数即可。 在最坏情况下,也就是假如要排序的元素为逆序,那么:元素比较的次数为:
元素交换的次数为:
总执行次数为:
按照大O推导法则,保留函数中的最高阶项那么最终冒泡排序的时间复杂度为O().

冒泡排序优化-鸡尾酒

  1. 当某一轮冒泡,不需要交换元素,说明数组此时已经有序,停止下轮比较
  1. 当数组部分有序时,单一方向冒泡,会导致更多轮排序
    1. notion image
      比如从左往右冒泡的时候,最小元素1靠右,需要排5轮
      排序轮次
      结果
      1
      234516
      2
      234156
      3
      231456
      4
      213456
      5
      123456
第一轮从左往右,第二轮从右往左,只需要三轮(第三轮发现不需要交换,数组已经有序,停止排序)
 
public static void optimizeSort(Comparable[] a) { //第一轮冒泡,最后一个元素为最大元素, for (int i = a.length - 1; i > 0; i--) { //比较0到倒数第二个元素 boolean leftSorted = true; for (int j = 0; j < i; j++) { if (greater(a[j], a[j + 1])) { exchange(a, j, j + 1); leftSorted = false; } } if (leftSorted){ break; } //反向冒泡 boolean rightSorted = true; for (int j = i; j > a.length - 1 - i; j--) { if (greater(a[j - 1], a[j])) { exchange(a, j - 1, j); rightSorted = false; } } if (rightSorted){ break; } } }

选择排序

选择排序Selection-sort是一种简单直观的排序算法

排序原理

首先在未排序序列中找到最小(大)元素,存放到排序序列的起始位置,然后,再从剩余未排序元素中继续寻找最小(大)元素,然后放到已排序序列的末尾。以此类推,直到所有元素均排序完毕。
 
需求: 排序前:{4,6,8,7,9,2,10,1} 排序后:{1,2,4,5,7,8,9,10}
算法描述
  1. 每一次遍历的过程中,都假定第一个索引处的元素是最小值,和其他索引处的值依次进行比较,如果当前索引处的值大于其他某个索引处的值,则假定其他某个索引出的值为最小值,最后可以找到最小值所在的索引。
  1. 交换第一个索引处和最小值所在的索引处的值。
notion image

API设计

public class SelectSort extends BaseSort { public static void main(String[] args) { int[] dataSize = {10000, 100000}; for (int n : dataSize) { Integer[] arr = ArrayGenerator.generateRandomArray(n, n); SortHelper.sortTest("com.onethink.sort.SelectSort", arr); } } @Override public <E extends Comparable<E>> void sort(E[] a) { for (int i = 0; i < a.length; i++) { int min = i; for (int j = i; j < a.length; j++) { if (a[min].compareTo(a[j]) > 0) { min = j; } } swap(a, min, i); } } }
 
时间复杂度分析
选择排序使用了双层for循环,其中外层循环完成了数据交换,内层循环完成了数据比较,所以我们分别统计数据交换次数和数据比较次数:数据比较次数:
数据交换次数:N-1
时间复杂度:
根据大O推导法则,保留最高阶项,去除常数因子,时间复杂度为O();
 
表现最稳定的排序算法之一,因为无论什么数据进去都是O()的时间复杂度,所以用到它的时候,数据规模越小越好。唯一的好处可能就是不占用额外的内存空间。
 

插入排序

插入排序(Insertion sort)是一种简单直观且稳定的排序算法。
插入排序的工作方式非常像人们排序一手扑克牌一样。开始时,我们的左手为空并且桌子上的牌面朝下。然后,我们每次从桌子上拿走一张牌并将它插入左手中正确的位置。为了找到一张牌的正确位置,我们从右到左将它与已在手中的每张牌进行比较。
 
需求:排序前:{4,3,2,10,12,1,5,6} 排序后:{1,2,3,4,5,6,10,12}

排序原理

  1. 把所有的元素分为两组,已经排序的和未排序的;
  1. 找到未排序的组中的第一个元素,向已经排序的组中进行插入;
  1. 倒叙遍历已经排序的元素,依次和待插入的元素进行比较,直到找到一个元素小于等于待插入元素,那么就把待插入元素放到这个位置,其他的元素向后移动一位
 
notion image

API设计

 
public class InsertSort extends BaseSort { @Override public <E extends Comparable<E>> void sort(E[] a) { //默认0为已经排序的,外层循环从1开始,代表未排序的 for (int i = 1; i < a.length; i++) { //倒序遍历已经排序的数组 for (int j = i; j > 0; j--) { //如果已经排序的数组元素大于未排序元素,则交换 if ((a[j - 1].compareTo(a[j])) > 0) { swap(a, j - 1, j); } else { //找到已经排序的数组元素小于等于未排序,则找到了待排序元素位置,停止遍历已经排序的数组 break; } } } } public static void main(String[] args) { int[] dataSize = {10000, 100000}; for (int n : dataSize) { Integer[] arr = ArrayGenerator.generateRandomArray(n, n); SortHelper.sortTest("com.onethink.sort.InsertSort", arr); } //com.onethink.sort.InsertSort算法,数据规模n = 10000 , 耗时0.095334 s //com.onethink.sort.InsertSort算法,数据规模n = 100000 , 耗时8.954800 s //根据结果 O(n) int[] dataSize2 = {10000, 100000}; for (int n : dataSize2) { Integer[] arr = ArrayGenerator.generateRandomArray(n, n); SortHelper.sortTest("com.onethink.sort.InsertSort2", arr); } // com.onethink.sort.InsertSort2算法,数据规模n = 10000 , 耗时0.087319 s // com.onethink.sort.InsertSort2算法,数据规模n = 100000 , 耗时7.186170 s }
 
 
 
插入排序使用了双层for循环,其中内层循环的循环体是真正完成排序的代码,所以,我们分析插入排序的时间复杂度,主要分析一下内层循环体的执行次数即可。
最坏情况,也就是待排序的数组元素为{12,10,6,5,4,3,2,1},那么:比较的次数为:
交换的次数为:
 
总执行次数为:
 
按照大O推导法则,保留函数中的最高阶项那么最终插入排序的时间复杂度为O().
 

小优化

public class InsertSort2 extends BaseSort { /** * 对插入排序的优化 优化swap操作,原有的swap需要操作三次 * 优化: 对于a[i] 元素 插入到[0,i-1]时候,如果a[i]小于已经排序的元素j, * 将[j-1,i-1]的元素移动一位,a[j]= a[i] * * @param a: * @return void * @author wangjie * @date 2023/3/8 22:12 * @since 1.0.0 */ @Override public <E extends Comparable<E>> void sort(E[] a) { //默认0为已经排序的,外层循环从1开始,代表未排序的 for (int i = 1; i < a.length; i++) { //倒序遍历已经排序的数组 E temp = a[i]; int j = i; for (; j > 0; j--) { //如果已经排序的数组元素大于未排序元素,则交换 if ((a[j - 1].compareTo(temp)) > 0) { a[j] = a[j - 1]; } else { //找到已经排序的数组元素小于等于未排序,则找到了待排序元素位置,停止遍历已经排序的数组 break; } // } a[j] = temp; } } }
 

最好时间复杂度

当数组本身有序的时候,插入排序的时间复杂度为O(n)

希尔排序

希尔排序是插入排序的一种,又称“缩小增量排序”,是插入排序算法的一种更高效的改进版本。它与插入排序的不同之处在于,它会优先比较距离较远的元素。
 
需求: 排序前:{9,1,2,5,7,4,8,6,3,5} 排序后:{1,2,3,4,5,5,6,7,8,9}

排序原理

1.选定一个增长量h,按照增长量h作为数据分组的依据,对数据进行分组;
2.对分好组的每一组数据完成插入排序;
3.减小增长量,最小减为1,重复第二步操作。
notion image
notion image
public class Shell { /* 对数组a中的元素进行排序 */ public static void sort(Comparable[] a){ //1.根据数组a的长度,确定增长量h的初始值; int h = 1; while(h<a.length/2){ h=2*h+1; } //2.希尔排序 while(h>=1){ //排序 //2.1.找到待插入的元素 for (int i=h;i<a.length;i++){ //2.2把待插入的元素插入到有序数列中 for (int j=i;j>=h;j-=h){ //待插入的元素是a[j],比较a[j]和a[j-h] if (greater(a[j-h],a[j])){ //交换元素 exch(a,j-h,j); }else{ //待插入元素已经找到了合适的位置,结束循环; break; } } } //减小h的值 h= h/2; } } /* 比较v元素是否大于w元素 */ private static boolean greater(Comparable v,Comparable w){ return v.compareTo(w)>0; } /* 数组元素i和j交换位置 */ private static void exch(Comparable[] a,int i,int j){ Comparable temp; temp = a[i]; a[i]=a[j]; a[j]=temp; } }
 

二路归并排序

归并排序是建立在归并操作上的一种有效的排序算法,该算法是采用分治法的一个非常典型的应用。将已有序的子序列合并,得到完全有序的序列;即先使每个子序列有序,再使子序列段间有序。若将两个有序表合并成一个有序表,称为二路归并。
需求: 排序前:{8,4,5,7,1,3,6,2} 排序后:{1,2,3,4,5,6,7,8}

排序原理

1.尽可能的一组数据拆分成两个元素相等的子组,并对每一个子组继续拆分,直到拆分后的每个子组的元素个数是1为止。 2.将相邻的两个子组进行合并成一个有序的大组; 3.不断的重复步骤2,直到最终只有一个组为止
notion image
 
最核心的merge代码,合并两个有序数组
notion image
notion image
notion image
notion image
notion image
notion image
notion image
notion image
从数列的角度来理解
归并排序
归并排序
API设计
notion image
public class Merge { //归并所需要的辅助数组 private static Comparable[] assist; /* 比较v元素是否小于w元素 */ private static boolean less(Comparable v, Comparable w) { return v.compareTo(w)<0; } /* 数组元素i和j交换位置 */ private static void exch(Comparable[] a, int i, int j) { Comparable t = a[i]; a[i] = a[j]; a[j] = t; } /* 对数组a中的元素进行排序 */ public static void sort(Comparable[] a) { //1.初始化辅助数组assist; assist = new Comparable[a.length]; //2.定义一个lo变量,和hi变量,分别记录数组中最小的索引和最大的索引; int lo=0; int hi=a.length-1; //3.调用sort重载方法完成数组a中,从索引lo到索引hi的元素的排序 sort(a,lo,hi); } /* 对数组a中从lo到hi的元素进行排序 */ private static void sort(Comparable[] a, int lo, int hi) { //做安全性校验; if (hi<=lo){ return; } //对lo到hi之间的数据进行分为两个组 int mid = lo+(hi-lo)/2;// 5,9 mid=7 //分别对每一组数据进行排序 sort(a,lo,mid); sort(a,mid+1,hi); //再把两个组中的数据进行归并 merge(a,lo,mid,hi); } /* 对数组中,从lo到mid为一组,从mid+1到hi为一组,对这两组数据进行归并 */ private static void merge(Comparable[] a, int lo, int mid, int hi) { //定义三个指针 int i=lo; int p1=lo; int p2=mid+1; //遍历,移动p1指针和p2指针,比较对应索引处的值,找出小的那个,放到辅助数组的对应索引处 while(p1<=mid && p2<=hi){ //比较对应索引处的值 if (less(a[p1],a[p2])){ assist[i++] = a[p1++]; }else{ assist[i++]=a[p2++]; } } //遍历,如果p1的指针没有走完,那么顺序移动p1指针,把对应的元素放到辅助数组的对应索引处 while(p1<=mid){ assist[i++]=a[p1++]; } //遍历,如果p2的指针没有走完,那么顺序移动p2指针,把对应的元素放到辅助数组的对应索引处 while(p2<=hi){ assist[i++]=a[p2++]; } //把辅助数组中的元素拷贝到原数组中 for(int index=lo;index<=hi;index++){ a[index]=assist[index]; } } }
归并排序时间复杂度分析:
归并排序是分治思想的最典型的例子,上面的算法中,对a[lo...hi]进行排序,先将它分为a[lo...mid]和a[mid+1...hi]两部分,分别通过递归调用将他们单独排序,最后将有序的子数组归并为最终的排序结果。该递归的出口在于如果一个数组不能再被分为两个子数组,那么就会执行merge进行归并,在归并的时候判断元素的大小进行排序。
notion image
用树状图来描述归并,如果一个数组有8个元素,那么它将每次除以2找最小的子数组,共拆log8次,值为3,所以树共有3层,
那么自顶向下第k层有个子数组,每个数组的长度为,归并最多需要次比较。因此每层的比较次数为 ,那么3层总共为
假设元素的个数为n,那么使用归并排序拆分的次数为log2(n),所以共log2(n)层,那么使用log2(n)替换上面中的3这个层数,最终得出的归并排序的时间复杂度为:
,根据大O推导法则,忽略底数,最终归并排序的时间复杂度为O(nlogn);
归并排序的缺点: 需要申请额外的数组空间,导致空间复杂度提升,是典型的空间换时间的操作

插入排序、希尔排序、归并排序性能比较:

测试数据文件夹下有一个reverse_arr.txt文件,里面存放的是从1000000到1的逆向数据,我们可以根据这个批量数据完成测试。测试的思想:在执行排序前前记录一个时间,在排序完成后记录一个时间,两个时间的时间差就是排序的耗时。
public class SortCompare { //调用不同的测试方法,完成测试 public static void main(String[] args) throws Exception{ //1.创建一个ArrayList集合,保存读取出来的整数 ArrayList<Integer> list = new ArrayList<>(); //2.创建缓存读取流BufferedReader,读取数据,并存储到ArrayList中; BufferedReader reader = new BufferedReader(new InputStreamReader(SortCompare.class.getClassLoader().getResourceAsStream("reverse_arr.txt"))); String line=null; while((line=reader.readLine())!=null){ //line是字符串,把line转换成Integer,存储到集合中 int i = Integer.parseInt(line); list.add(i); } reader.close(); //3.把ArrayList集合转换成数组 Integer[] a = new Integer[list.size()]; list.toArray(a); //4.调用测试代码完成测试 // testInsertion(a);//37184毫秒 testShell(a);//32毫秒 // testMerge(a);//31毫秒 } //测试希尔排序 public static void testShell(Integer[] a){ //1.获取执行之前的时间 long start = System.currentTimeMillis(); //2.执行算法代码 Shell.sort(a); //3.获取执行之后的时间 long end = System.currentTimeMillis(); //4.算出程序执行的时间并输出 System.out.println("希尔排序执行的时间为:"+(end-start)+"毫秒"); } //测试插入排序 public static void testInsertion(Integer[] a){ //1.获取执行之前的时间 long start = System.currentTimeMillis(); //2.执行算法代码 Insertion.sort(a); //3.获取执行之后的时间 long end = System.currentTimeMillis(); //4.算出程序执行的时间并输出 System.out.println("插入排序执行的时间为:"+(end-start)+"毫秒"); } //测试归并排序 public static void testMerge(Integer[] a){ //1.获取执行之前的时间 long start = System.currentTimeMillis(); //2.执行算法代码 Merge.sort(a); //3.获取执行之后的时间 long end = System.currentTimeMillis(); //4.算出程序执行的时间并输出 System.out.println("归并排序执行的时间为:"+(end-start)+"毫秒"); } }

多路归并排序

待续

快排

快速排序是对冒泡排序的一种改进。它的基本思想是:通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列。
需求: 排序前:{6, 1, 2, 7, 9, 3, 4, 5, 8} 排序后:{1, 2, 3, 4, 5, 6, 7, 8, 9}

排序原理

1.首先设定一个分界值,通过该分界值将数组分成左右两部分; 2.将大于或等于分界值的数据放到到数组右边,小于分界值的数据放到数组的左边。此时左边部分中各元素都小于或等于分界值,而右边部分中各元素都大于或等于分界值;
3.然后,左边和右边的数据可以独立排序。对于左侧的数组数据,又可以取一个分界值,将该部分数据分成左右两部分,同样在左边放置较小值,右边放置较大值。右侧的数组数据也可以做类似处理。 4.重复上述过程,可以看出,这是一个递归定义。通过递归将左侧部分排好序后,再递归排好右侧部分的顺序。当左侧和右侧两个部分的数据排完序后,整个数组的排序也就完成了。
notion image
分组找中间值
notion image
notion image
notion image
notion image
notion image

API设计

notion image
public class Quick { /* 比较v元素是否小于w元素 */ private static boolean less(Comparable v, Comparable w) { return v.compareTo(w) < 0; } /* 数组元素i和j交换位置 */ private static void exch(Comparable[] a, int i, int j) { Comparable t = a[i]; a[i] = a[j]; a[j] = t; } //对数组内的元素进行排序 public static void sort(Comparable[] a) { int lo = 0; int hi = a.length-1; sort(a,lo,hi); } //对数组a中从索引lo到索引hi之间的元素进行排序 private static void sort(Comparable[] a, int lo, int hi) { //安全性校验 if (hi<=lo){ return; } //需要对数组中lo索引到hi索引处的元素进行分组(左子组和右子组); int partition = partition(a, lo, hi);//返回的是分组的分界值所在的索引,分界值位置变换后的索引 //让左子组有序 sort(a,lo,partition-1); //让右子组有序 sort(a,partition+1,hi); } //对数组a中,从索引 lo到索引 hi之间的元素进行分组,并返回分组界限对应的索引 public static int partition(Comparable[] a, int lo, int hi) { //确定分界值 Comparable key = a[lo]; //定义两个指针,分别指向待切分元素的最小索引处和最大索引处的下一个位置 int left=lo; int right=hi+1; //切分 while(true){ //先从右往左扫描,移动right指针,找到一个比分界值小的元素,停止 while(less(key,a[--right])){ if (right==lo){ break; } } //再从左往右扫描,移动left指针,找到一个比分界值大的元素,停止 while(less(a[++left],key)){ if (left==hi){ break; } } //判断 left>=right,如果是,则证明元素扫描完毕,结束循环,如果不是,则交换元素即可 if (left>=right){ break; }else{ exch(a,left,right); } } //交换分界值 exch(a,lo,right); return right; } }
快速排序时间复杂度分析:
快速排序的一次切分从两头开始交替搜索,直到left和right重合,因此,一次切分算法的时间复杂度为O(n),但整个快速排序的时间复杂度和切分的次数相关。 最优情况:每一次切分选择的基准数字刚好将当前序列等分。
notion image
如果我们把数组的切分看做是一个树,那么上图就是它的最优情况的图示,共切分了logn次,所以,最优情况下快速排序的时间复杂度为O(nlogn); 最坏情况:每一次切分选择的基准数字是当前序列中最大数或者最小数,这使得每次切分都会有一个子组,那么总共就得切分n次,所以,最坏情况下,快速排序的时间复杂度为O();

快速排序和归并排序的区别

快速排序是另外一种分治的排序算法,它将一个数组分成两个子数组,将两部分独立的排序。快速排序和归并排序是互补的:
归并排序将数组分成两个子数组分别排序,并将有序的子数组归并从而将整个数组排序,而快速排序的方式则是当两个数组都有序时,整个数组自然就有序了。在归并排序中,一个数组被等分为两半,归并调用发生在处理整个数组之前,在快速排序中,切分数组的位置取决于数组的内容,递归调用发生在处理整个数组之后。

快速排序优化

基准值取两端的话,在特殊情况一下,会导致更容易StackOverFlow
比如数组是逆序的,需要顺序排列,此时0号为基准值,则每次的分区后基准值都是数组的索引降序,如果数组的长度超过编程语言的栈深度,则会报错
 
/** * 1。 left指针从左到右,找到比基准值大的则停止 * 2。 right指针从右到左,找到比基准值小的则停止 * 3。 交换left,right的值, * 4。 重复上述步骤,直到left>=right * 5。 交互right处索引和基准值 * 6。 right为新的基准索引 * * @param arr: 原数组 * @param lo: 分组的开始索引 * @param hi: 分组的结束索引 * @return int: 返回的基准值索引 * @author wangjie * @date 2022/12/28 10:06 * @since 1.0.0 */ private static int partition(Comparable[] arr, int lo, int hi) { int k = (lo + hi) / 2; int left = lo - 1; int right = hi + 1; while (true) { while (greater(arr[k], arr[++left])) { if (left == hi) { break; } } while (greater(arr[--right], arr[k])) { if (right == lo) { break; } } if (left >= right) { break; } else { exchange(arr, left, right); } } exchange(arr, k, right); return right; }

堆排序

给定一个数组: String[] arr = {"S","O","R","T","E","X","A","M","P","L","E"} 请对数组中的字符按从小到大排序。 实现步骤: 1.构造堆; 2.得到堆顶元素,这个值就是最大值; 3.交换堆顶元素和数组中的最后一个元素,此时所有元素中的最大元素已经放到合适的位置; 4.对堆进行调整,重新让除了最后一个元素的剩余元素中的最大值放到堆顶; 5.重复2~4这个步骤,直到堆中剩一个元素为止。
notion image

堆构造过程

堆的构造,最直观的想法就是另外再创建一个和新数组数组,然后从左往右遍历原数组,每得到一个元素后,添加到新数组中,并通过上浮,对堆进行调整,最后新的数组就是一个堆。 上述的方式虽然很直观,也很简单,但是我们可以用更聪明一点的办法完成它。创建一个新数组,把原数组0~length-1的数据拷贝到新数组的1~length处,再从新数组长度的一半处开始往1索引处扫描(从右往左),然后对扫描到的每一个元素做下沉调整即可。
notion image
notion image
notion image
notion image
notion image
notion image

堆排序过程

对构造好的堆,我们只需要做类似于堆的删除操作,就可以完成排序。
  1. 将堆顶元素和堆中最后一个元素交换位置;
  1. 通过对堆顶元素下沉调整堆,把最大的元素放到堆顶(此时最后一个元素不参与堆的调整,因为最大的数据已经到了数组的最右边)
  1. 重复1~2步骤,直到堆中剩最后一个元素。
notion image
notion image
notion image
notion image
notion image
notion image
 
public class HeapSort { //判断heap堆中索引i处的元素是否小于索引j处的元素 private static boolean less(Comparable[] heap, int i, int j) { return heap[i].compareTo(heap[j])<0; } //交换heap堆中i索引和j索引处的值 private static void exch(Comparable[] heap, int i, int j) { Comparable tmp = heap[i]; heap[i] = heap[j]; heap[j] = tmp; } //根据原数组source,构造出堆heap private static void createHeap(Comparable[] source, Comparable[] heap) { //把source中的元素拷贝到heap中,heap中的元素就形成一个无序的堆 System.arraycopy(source,0,heap,1,source.length); //对堆中的元素做下沉调整(从长度的一半处开始,往索引1处扫描) for (int i = (heap.length)/2;i>0;i--){ sink(heap,i,heap.length-1); } } //对source数组中的数据从小到大排序 public static void sort(Comparable[] source) { //构建堆 Comparable[] heap = new Comparable[source.length+1]; createHeap(source,heap); //定义一个变量,记录未排序的元素中最大的索引 int N = heap.length-1; //通过循环,交换1索引处的元素和排序的元素中最大的索引处的元素 while(N!=1){ //交换元素 exch(heap,1,N); //排序交换后最大元素所在的索引,让它不要参与堆的下沉调整 N--; //需要对索引1处的元素进行对的下沉调整 sink(heap,1, N); } //把heap中的数据复制到原数组source中 System.arraycopy(heap,1,source,0,source.length); } //在heap堆中,对target处的元素做下沉,范围是0~range private static void sink(Comparable[] heap, int target, int range){ while(2*target<=range){ //1.找出当前结点的较大的子结点 int max; if (2*target+1<=range){ if (less(heap,2*target,2*target+1)){ max = 2*target+1; }else{ max = 2*target; } }else{ max = 2*target; } //2.比较当前结点的值和较大子结点的值 if (!less(heap,target,max)){ break; } exch(heap,target,max); target = max; } } }

桶排序

 

排序的稳定性

稳定性的定义: 数组arr中有若干元素,其中A元素和B元素相等,并且A元素在B元素前面,如果使用某种排序算法排序后,能够保证A元素依然在B元素的前面,可以说这个该算法是稳定的。
notion image
稳定性的意义: 如果一组数据只需要一次排序,则稳定性一般是没有意义的,如果一组数据需要多次排序,稳定性是有意义的。例如要排序的内容是一组商品对象,第一次排序按照价格由低到高排序,第二次排序按照销量由高到低排序,如果第二次排序使用稳定性算法,就可以使得相同销量的对象依旧保持着价格高低的顺序展现,只有销量不同的对象才需要重新排序。这样既可以保持第一次排序的原有意义,而且可以减少系统开销。
 

常见排序算法的稳定性

冒泡排序: 只有当arr[i]>arr[i+1]的时候,才会交换元素的位置,而相等的时候并不交换位置,所以冒泡排序是一种稳定排序算法。
选择排序: 选择排序是给每个位置选择当前元素最小的,例如有数据{5(1),8 ,5(2), 2, 9 },第一遍选择到的最小元素为2,所以5(1)会和2进行交换位置,此时5(1)到了5(2)后面,破坏了稳定性,所以选择排序是一种不稳定的排序算法。
插入排序: 比较是从有序序列的末尾开始,也就是想要插入的元素和已经有序的最大者开始比起,如果比它大则直接插入在其后面,否则一直往前找直到找到它该插入的位置。如果碰见一个和插入元素相等的,那么把要插入的元素放在相等元素的后面。所以,相等元素的前后顺序没有改变,从原无序序列出去的顺序就是排好序后的顺序,所以插入排序是稳定的。
希尔排序:
希尔排序是按照不同步长对元素进行插入排序 ,虽然一次插入排序是稳定的,不会改变相同元素的相对顺序,但在不同的插入排序过程中,相同的元素可能在各自的插入排序中移动,最后其稳定性就会被打乱,所以希尔排序是不稳定的。
归并排序: 归并排序在归并的过程中,只有arr[i]<arr[i+1]的时候才会交换位置,如果两个元素相等则不会交换位置,所以它并不会破坏稳定性,归并排序是稳定的。
快速排序: 快速排序需要一个基准值,在基准值的右侧找一个比基准值小的元素,在基准值的左侧找一个比基准值大的元素,然后交换这两个元素,此时会破坏稳定性,所以快速排序是一种不稳定的算法

各大排序算法复杂度总览

各大排序算法复杂度总览
各大排序算法复杂度总览
相关概念
  • 稳定:如果a原本在b前面,而a=b,排序之后a仍然在b的前面。
  • 不稳定:如果a原本在b的前面,而a=b,排序之后 a 可能会出现在 b 的后面。
  • 时间复杂度:对排序数据的总的操作次数。反映当n变化时,操作次数呈现什么规律。
  • 空间复杂度:是指算法在计算机内执行时所需存储空间的度量,它也是数据规模n的函数。