什么是网站交互性,成都网站建设推来客熊掌号,抖音代运营是什么意思,重庆百度竞价推广03_排序 一、简单排序Comparable接口介绍需求#xff1a; 冒泡排序排序原理#xff1a;冒泡排序API设计#xff1a; 选择排序排序原理#xff1a;选择排序API设计#xff1a;选择排序的时间复杂度分析#xff1a; 插入排序需求#xff1a;排序原理#xff1a;插入排序A… 03_排序 一、简单排序Comparable接口介绍需求 冒泡排序排序原理冒泡排序API设计 选择排序排序原理选择排序API设计选择排序的时间复杂度分析 插入排序需求排序原理插入排序API设计插入排序的时间复杂度分析 二、高级排序希尔排序需求排序原理希尔排序的API设计希尔排序和插入排序性能比较测试代码 归并排序递归作用注意事项需求 归并排序需求排序原理归并排序API设计归并排序代码实现归并排序时间复杂度分析归并排序的缺点**归并排序与希尔排序性能测试**希尔排序和插入排序性能比较测试代码 快速排序需求排序原理快速排序API设计:快速排序代码实现快速排序和归并排序的区别快速排序时间复杂度分析 排序的稳定性稳定性的定义稳定性的意义 一、简单排序
在我们的程序中排序是非常常见的一种需求提供一些数据元素把这些数据元素按照一定的规则进行排序。比 如查询一些订单按照订单的日期进行排序再比如查询一些商品按照商品的价格进行排序等等。所以接下来 我们要学习一些常见的排序算法。在java的开发工具包jdk中已经给我们提供了很多数据结构与算法的实现比如ListSetMapMath等等都 是以API的方式提供这种方式的好处在于一次编写多处使用。我们借鉴jdk的方式也把算法封装到某个类中 那如果是这样在我们写java代码之前就需要先进行API的设计设计好之后再对这些API进行实现。就比如我们先设计一套API如下
类名ArrayList构造方法ArrayList()创建ArrayList对象成员方法1.boolean add(E e)向集合中添加元素2.E remove(int index):从集合中删除指定的元素
然后再使用java代码去实现它。以后我们讲任何数据结构与算法都是以这种方式讲解
Comparable接口介绍
由于我们这里要讲排序所以肯定会在元素之间进行比较而Java提供了一个接口Comparable就是用来定义排序 规则的在这里我们以案例的形式对Comparable接口做一个简单的回顾。
需求
定义一个学生类Student具有年龄age和姓名username两个属性并通过Comparable接口提供比较规则定义测试类Test在测试类Test中定义测试方法Comparable getMax(Comparable c1,Comparable c2)完成测试
//学生类
public class Student implements ComparableStudent{private String username;private int age;public String getUsername() {return username;}public void setUsername(String username) {this.username username;}public int getAge() {return age;}public void setAge(int age) {this.age age;}Overridepublic String toString() {return Student{ username username \ , age age };}//定义比较规则Overridepublic int compareTo(Student o) {return this.getAge()-o.getAge();}
}
//测试类
public class Test {public static void main(String[] args) {Student stu1 new Student();stu1.setUsername(zhangsan);stu1.setAge(17);Student stu2 new Student();stu2.setUsername(lisi);stu2.setAge(19);Comparable max getMax(stu1, stu2);System.out.println(max);}//测试方法获取两个元素中的较大值public static Comparable getMax(Comparable c1,Comparable c2){int cmp c1.compareTo(c2);if (cmp0){return c1;}else{return c2;}}
}冒泡排序
冒泡排序Bubble Sort是一种计算机科学领域的较简单的排序算法。需求排序前{4,5,6,3,2,1}
序后{1,2,3,4,5,6}
排序原理 1. 比较相邻的元素。如果前一个元素比后一个元素大就交换这两个元素的位置。2. 对每一对相邻元素做同样的工作从开始第一对元素到结尾的最后一对元素。最终最后位置的元素就是最大 值。冒泡排序API设计
类名Bubble构造方法Bubble()创建Bubble对象成员方法1. public static void sort(Comparable[] a)对数组内的元素进行排序2. private static boolean greater(Comparable v,Comparable w):判断v是否大于w 3. 3.private static void exch(Comparable[] a,int i,int j)交换a数组中索引i和索引j处的值
冒泡排序的代码实现
//排序代码
public class Bubble {/*
对数组a中的元素进行排序
*/public static void sort(Comparable[] a){for(int ia.length-1;i0;i--){for (int j 0; j i; j) {if (greater(a[j],a[j1])){exch(a,j,j1);}}}}/*
比较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 t a[i];a[i]a[j];a[j]t;}
}
//测试代码
public class Test {public static void main(String[] args) {Integer[] a {4, 5, 6, 3, 2, 1};Bubble.sort(a);System.out.println(Arrays.toString(a));}
}
**冒泡排序的时间复杂度分析 **冒泡排序使用了双层for循环其中内层循环的循环体是真正完成排序的代码所以 我们分析冒泡排序的时间复杂度主要分析一下内层循环体的执行次数即可。在最坏情况下也就是假如要排序的元素为{6,5,4,3,2,1}逆序那么 元素比较的次数为(N-1)(N-2)(N-3)…21((N-1)1)(N-1)/2N^2/2-N/2;元素交换的次数为(N-1)(N-2)(N-3)…21((N-1)1)(N-1)/2N^2/2-N/2;总执行次数为(N2/2-N/2)(N2/2-N/2)N^2-N;按照大O推导法则保留函数中的最高阶项那么最终冒泡排序的时间复杂度为O(N^2). 选择排序
选择排序是一种更加简单直观的排序方法。需求排序前{4,6,8,7,9,2,10,1}排序后{1,2,4,5,7,8,9,10}
排序原理
每一次遍历的过程中都假定第一个索引处的元素是最小值和其他索引处的值依次进行比较如果当前索引处 的值大于其他某个索引处的值则假定其他某个索引出的值为最小值最后可以找到最小值所在的索引交换第一个索引处和最小值所在的索引处的值 选择排序API设计
类名Selection构造方法Selection()创建Selection对象成员方法1. public static void sort(Comparable[] a)对数组内的元素进行排序2. private static boolean greater(Comparable v,Comparable w):判断v是否大于w 3. 3.private static void exch(Comparable[] a,int i,int j)交换a数组中索引i和索引j处的值
选择排序的代码实现
// 排序代码
public class Selection {/*对数组a中的元素进行排序*/public static void sort(Comparable[] a){for (int i0;ia.length-2;i){//假定本次遍历最小值所在的索引是iint minIndexi;for (int ji1;ja.length;j){if (greater(a[minIndex],a[j])){//跟换最小值所在的索引minIndexj;}}//交换i索引处和minIndex索引处的值exch(a,i,minIndex);}}/*比较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 t a[i];a[i]a[j];a[j]t;}
}
//测试代码
public class Test {public static void main(String[] args) {Integer[] a {4,6,8,7,9,2,10,1};Selection.sort(a);System.out.println(Arrays.toString(a));}
}选择排序的时间复杂度分析
选择排序使用了双层for循环其中外层循环完成了数据交换内层循环完成了数据比较所以我们分别统计数据 交换次数和数据比较次数数据比较次数(N-1)(N-2)(N-3)…21((N-1)1)*(N-1)/2N^2/2-N/2;
据交换次数N-1
时间复杂度N2/2-N/2N-1N2/2N/2-1;根据大O推导法则保留最高阶项去除常数因子时间复杂度为O(N^2); 插入排序
插入排序Insertion sort是一种简单直观且稳定的排序算法。插入排序的工作方式非常像人们排序一手扑克牌一样。开始时我们的左手为空并且桌子上的牌面朝下。然后我 们每次从桌子上拿走一张牌并将它插入左手中正确的位置。为了找到一张牌的正确位置我们从右到左将它与已在 手中的每张牌进行比较如下图所示
需求
排序前{4,3,2,10,12,1,5,6}排序后{1,2,3,4,5,6,10,12}
排序原理
把所有的元素分为两组已经排序的和未排序的找到未排序的组中的第一个元素向已经排序的组中进行插入倒叙遍历已经排序的元素依次和待插入的元素进行比较直到找到一个元素小于等于待插入元素那么就把待 插入元素放到这个位置其他的元素向后移动一位 插入排序API设计
类名Insertion构造方法Insertion()创建Insertion对象成员方法1. public static void sort(Comparable[] a)对数组内的元素进行排序2. private static boolean greater(Comparable v,Comparable w):判断v是否大于w 3. 3.private static void exch(Comparable[] a,int i,int j)交换a数组中索引i和索引j处的值
插入排序代码实现
public class Insertion {/*
对数组a中的元素进行排序
*/public static void sort(Comparable[] a){for (int i1;ia.length;i){//当前元素为a[i],依次和i前面的元素比较找到一个小于等于a[i]的元素for (int ji;j0;j--){if (greater(a[j-1],a[j])){//交换元素exch(a,j-1,j);}else {//找到了该元素结束break;}}}}/*
比较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 t a[i];a[i]a[j];a[j]t;}
}插入排序的时间复杂度分析
插入排序使用了双层for循环其中内层循环的循环体是真正完成排序的代码所以我们分析插入排序的时间复 杂度主要分析一下内层循环体的执行次数即可。最坏情况也就是待排序的数组元素为{12,10,6,5,4,3,2,1}那么 比较的次数为(N-1)(N-2)(N-3)…21((N-1)1)(N-1)/2N^2/2-N/2;交换的次数为(N-1)(N-2)(N-3)…21((N-1)1)(N-1)/2N^2/2-N/2;总执行次数为(N2/2-N/2)(N2/2-N/2)N^2-N;按照大O推导法则保留函数中的最高阶项那么最终插入排序的时间复杂度为O(N^2).
二、高级排序
之前我们学习过基础排序包括冒泡排序选择排序还有插入排序并且对他们在最坏情况下的时间复杂度做了分 析发现都是O(N^2)而平方阶通过我们之前学习算法分析我们知道随着输入规模的增大时间成本将急剧上 升所以这些基本排序方法不能处理更大规模的问题接下来我们学习一些高级的排序算法争取降低算法的时间 复杂度最高阶次幂。
希尔排序
希尔排序是插入排序的一种又称“缩小增量排序”是插入排序算法的一种更高效的改进版本。
前面学习插入排序的时候我们会发现一个很不友好的事儿如果已排序的分组元素为{2,5,7,9,10}未排序的分组 元素为{1,8}那么下一个待插入元素为1我们需要拿着1从后往前依次和10,9,7,5,2进行交换位置才能完成真 正的插入每次交换只能和相邻的元素交换位置。那如果我们要提高效率直观的想法就是一次交换能把1放到 更前面的位置比如一次交换就能把1插到2和5之间这样一次交换1就向前走了5个位置可以减少交换的次数 这样的需求如何实现呢接下来我们来看看希尔排序的原理。
需求
排序前{9,1,2,5,7,4,8,6,3,5}排序后{1,2,3,4,5,5,6,7,8,9}
排序原理
选定一个增长量h按照增长量h作为数据分组的依据对数据进行分组对分好组的每一组数据完成插入排序减小增长量最小减为1重复第二步操作。 增长量h的确定增长量h的值每一固定的规则我们这里采用以下规则 int h1
while(h5){h2h1//3,7
}
//循环结束后我们就可以确定h的最大值
h的减小规则为
hh/2希尔排序的API设计
类名Shell构造方法Shell()创建Shell对象成员方法1. public static void sort(Comparable[] a)对数组内的元素进行排序2. private static boolean greater(Comparable v,Comparable w):判断v是否大于w 3. 3.private static void exch(Comparable[] a,int i,int j)交换a数组中索引i和索引j处的值
希尔排序的代码实现
//排序代码
public class Shell {/*
对数组a中的元素进行排序
*/public static void sort(Comparable[] a){int N a.length;//确定增长量h的最大值int h1;while(hN/2){hh*21;}//当增长量h小于1排序结束while(h1){//找到待插入的元素for (int ih;iN;i){//a[i]就是待插入的元素//把a[i]插入到a[i-h],a[i-2h],a[i-3h]...序列中for (int ji;jh;j-h){//a[j]就是待插入元素依次和a[j-h],a[j-2h],a[j-3h]进行比较如果a[j]小那么交换位置如果不小于a[j]大则插入完成。if (greater(a[j-h],a[j])){exch(a,j,j-h);}else{break;}}}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 t a[i];a[i]a[j];a[j]t;}
}
//测试代码
public class Test {public static void main(String[] args) {Integer[] a {9,1,2,5,7,4,8,6,3,5} ;Shell.sort(a);System.out.println(Arrays.toString(a));}
}希尔排序的时间复杂度分析在希尔排序中增长量h并没有固定的规则有很多论文研究了各种不同的递增序列但都无法证明某个序列是最 好的对于希尔排序的时间复杂度分析已经超出了我们课程设计的范畴所以在这里就不做分析了。我们可以使用事后分析法对希尔排序和插入排序做性能比较。在资料的测试数据文件夹下有一个reverse_shell_insertion.txt文件里面存放的是从100000到1的逆向数据我们 可以根据这个批量数据完成测试。测试的思想在执行排序前前记录一个时间在排序完成后记录一个时间两个 时间的时间差就是排序的耗时。
希尔排序和插入排序性能比较测试代码
public class SortCompare {public static void main(String[] args) throws Exception{ArrayListInteger list new ArrayList();//读取reverse_arr.txt文件BufferedReader reader new BufferedReader(new InputStreamReader(newFileInputStream(reverse_shell_insertion.txt)));String linenull;while((linereader.readLine())!null){//把每一个数字存入到集合中list.add(Integer.valueOf(line));}reader.close();//把集合转换成数组Integer[] arr new Integer[list.size()];list.toArray(arr);testInsertion(arr);//使用插入排序耗时20859// testShell(arr);//使用希尔排序耗时31}public static void testInsertion(Integer[] arr){//使用插入排序完成测试long start System.currentTimeMillis();Insertion.sort(arr);long end System.currentTimeMillis();System.out.println(使用插入排序耗时(end-start));}public static void testShell(Integer[] arr){//使用希尔排序完成测试long start System.currentTimeMillis();Shell.sort(arr);long end System.currentTimeMillis();System.out.println(使用希尔排序耗时(end-start));}
}通过测试发现在处理大批量数据时希尔排序的性能确实高于插入排序。
归并排序 递归
正式学习归并排序之前我们得先学习一下递归算法。定义定义方法时在方法内部调用方法本身称之为递归.
public void show(){System.out.println(aaaa);show();
}作用
它通常把一个大型复杂的问题层层转换为一个与原问题相似的规模较小的问题来求解。递归策略只需要少量的 程序就可以描述出解题过程所需要的多次重复计算大大地减少了程序的代码量。
注意事项
在递归中不能无限制的调用自己必须要有边界条件能够让递归结束因为每一次递归调用都会在栈内存开辟 新的空间重新执行方法如果递归的层级太深很容易造成栈内存溢出。
需求
请定义一个方法使用递归完成求N的阶乘
分析
1!: 1
2!: 2*12*1!
3!: 3*2*13*2!
4!: 4*3*2*14*3!
...
n!: n*(n-1)*(n-2)...*2*1n*(n-1)!
所以假设有一个方法factorial(n)用来求n的阶乘那么n的阶乘还可以表示为n*factorial(n-1)代码实现
public class Test {public static void main(String[] args) throws Exception {int result factorial(5);System.out.println(result);}public static int factorial(int n){if (n1){return 1;}return n*factorial(n-1);}
}归并排序
归并排序是建立在归并操作上的一种有效的排序算法该算法是采用分治法的一个非常典型的应用。将已有序的子 序列合并得到完全有序的序列即先使每个子序列有序再使子序列段间有序。若将两个有序表合并成一个有序 表称为二路归并。
需求
排序前{8,4,5,7,1,3,6,2}排序后{1,2,3,4,5,6,7,8}
排序原理
尽可能的一组数据拆分成两个元素相等的子组并对每一个子组继续拆分直到拆分后的每个子组的元素个数是
1为止。
将相邻的两个子组进行合并成一个有序的大组不断的重复步骤2直到最终只有一个组为止。 归并排序API设计
类名Merge构造方法Merge()创建Merge对象成员方法1. public static void sort(Comparable[] a)对数组内的元素进行排序2. private static void sort(Comparable[] a, int lo, int hi)对数组a中从索引lo到索引hi之间的元素进行排序3. private static void merge(Comparable[] a, int lo, int mid, int hi):从索引lo到所以mid为一个子组从索引mid1到索引hi为另一个子组把数组a中的这两个子组的数据合并成一个有序的大组从 索引lo到索引hi4. private static boolean less(Comparable v,Comparable w):判断v是否小于w5. private static void exch(Comparable[] a,int i,int j)交换a数组中索引i和索引j处的值成员变量1.private static Comparable[] assist完成归并操作需要的辅助数组
归并原理 归并排序代码实现
//排序代码
public class Merge {private static Comparable[] assist;//归并所需要的辅助数组/*
对数组a中的元素进行排序
*/public static void sort(Comparable[] a) {assist new Comparable[a.length];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;}int mid lo (hi - lo) / 2;//对lo到mid之间的元素进行排序sort(a, lo, mid);//对mid1到hi之间的元素进行排序sort(a, mid1, hi);//对lo到mid这组数据和mid到hi这组数据进行归并merge(a, lo, mid, hi);}/*
对数组中从lo到mid为一组从mid1到hi为一组对这两组数据进行归并
*/private static void merge(Comparable[] a, int lo, int mid, int hi) {//lo到mid这组数据和mid1到hi这组数据归并到辅助数组assist对应的索引处int i lo;//定义一个指针指向assist数组中开始填充数据的索引int p1 lo;//定义一个指针指向第一组数据的第一个元素int p2 mid 1;//定义一个指针指向第二组数据的第一个元素//比较左边小组和右边小组中的元素大小哪个小就把哪个数据填充到assist数组中while (p1 mid p2 hi) {if (less(a[p1], a[p2])) {assist[i] a[p1];} else {assist[i] a[p2];}}//上面的循环结束后如果退出循环的条件是p1mid则证明左边小组中的数据已经归并完毕如果退出循环的条件是p2hi,则证明右边小组的数据已经填充完毕//所以需要把未填充完毕的数据继续填充到assist中,//下面两个循环只会执行其中的一个while(p1mid){assist[i]a[p1];}while(p2hi){assist[i]a[p2];}//到现在为止assist数组中从lo到hi的元素是有序的再把数据拷贝到a数组中对应的索引处for (int indexlo;indexhi;index){a[index]assist[index];}}/*
比较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 class Test {public static void main(String[] args) throws Exception {Integer[] arr {8, 4, 5, 7, 1, 3, 6, 2};Merge.sort(arr);System.out.println(Arrays.toString(arr));}
} 归并排序时间复杂度分析
归并排序是分治思想的最典型的例子上面的算法中对a[lo…hi]进行排序先将它分为a[lo…mid]和a[mid1…hi] 两部分分别通过递归调用将他们单独排序最后将有序的子数组归并为最终的排序结果。该递归的出口在于如果 一个数组不能再被分为两个子数组那么就会执行merge进行归并在归并的时候判断元素的大小进行排序。
用树状图来描述归并如果一个数组有8个元素那么它将每次除以2找最小的子数组共拆log8次值为3所以 树共有3层,那么自顶向下第k层有2k个子数组每个数组的长度为2(3-k)归并最多需要2^(3-k)次比较。因此每层 的比较次数为 2^k * 2(3-k)23,那么3层总共为 32^3。假设元素的个数为n那么使用归并排序拆分的次数为log2(n),所以共log2(n)层那么使用log2(n)替换上面32^3中 的3这个层数最终得出的归并排序的时间复杂度为log2(n)* 2^(log2(n))log2(n)*n,根据大O推导法则忽略底数最终归并排序的时间复杂度为O(nlogn);
归并排序的缺点
需要申请额外的数组空间导致空间复杂度提升是典型的以空间换时间的操作。
归并排序与希尔排序性能测试
之前我们通过测试可以知道希尔排序的性能是由于插入排序的那现在学习了归并排序后归并排序的效率与希尔 排序的效率哪个高呢我们使用同样的测试方式来完成一样这两个排序算法之间的性能比较。在资料的测试数据文件夹下有一个reverse_arr.txt文件里面存放的是从1000000到1的逆向数据我们可以根据 这个批量数据完成测试。测试的思想在执行排序前前记录一个时间在排序完成后记录一个时间两个时间的时 间差就是排序的耗时。
希尔排序和插入排序性能比较测试代码
public class SortCompare {public static void main(String[] args) throws Exception{ArrayListInteger list new ArrayList();//读取a.txt文件BufferedReader reader new BufferedReader(new InputStreamReader(new FileInputStream(reverse_merge_shell.txt)));String linenull;while((linereader.readLine())!null){//把每一个数字存入到集合中list.add(Integer.valueOf(line));}reader.close();//把集合转换成数组Integer[] arr new Integer[list.size()];list.toArray(arr);// testMerge(arr);//使用归并排序耗时1200testShell(arr);//使用希尔排序耗时1277}public static void testMerge(Integer[] arr){//使用插入排序完成测试long start System.currentTimeMillis();Merge.sort(arr);long end System.currentTimeMillis();System.out.println(使用归并排序耗时(end-start));}public static void testShell(Integer[] arr){//使用希尔排序完成测试long start System.currentTimeMillis();Shell.sort(arr);long end System.currentTimeMillis();System.out.println(使用希尔排序耗时(end-start));}
}
通过测试发现希尔排序和归并排序在处理大批量数据时差别不是很大。
快速排序
快速排序是对冒泡排序的一种改进。它的基本思想是通过一趟排序将要排序的数据分割成独立的两部分其中一 部分的所有数据都比另外一部分的所有数据都要小然后再按此方法对这两部分数据分别进行快速排序整个排序 过程可以递归进行以此达到整个数据变成有序序列。
需求
排序前:{6, 1, 2, 7, 9, 3, 4, 5, 8}排序后:{1, 2, 3, 4, 5, 6, 7, 8, 9}
排序原理
首先设定一个分界值通过该分界值将数组分成左右两部分将大于或等于分界值的数据放到到数组右边小于分界值的数据放到数组的左边。此时左边部分中各元素都小于 或等于分界值而右边部分中各元素都大于或等于分界值后左边和右边的数据可以独立排序。对于左侧的数组数据又可以取一个分界值将该部分数据分成左右两 部分同样在左边放置较小值右边放置较大值。右侧的数组数据也可以做类似处理。重复上述过程可以看出这是一个递归定义。通过递归将左侧部分排好序后再递归排好右侧部分的顺序。当 左侧和右侧两个部分的数据排完序后整个数组的排序也就完成了。 快速排序API设计:
类名Quick构造方法Quick()创建Quick对象成员方法1. public static void sort(Comparable[] a)对数组内的元素进行排序2. private static void sort(Comparable[] a, int lo, int hi)对数组a中从索引lo到索引hi之间的元素进行排序3. public static int partition(Comparable[] a,int lo,int hi):对数组a中从索引 lo到索引 hi之间的元素进行分组并返回分组界限对应的索引4. private static boolean less(Comparable v,Comparable w):判断v是否小于w
private static void exch(Comparable[] a,int i,int j)交换a数组中索引i和索引j处的值 |
切分原理把一个数组切分成两个子数组的基本思想
找一个基准值用两个指针分别指向数组的头部和尾部先从尾部向头部开始搜索一个比基准值小的元素搜索到即停止并记录指针的位置再从头部向尾部开始搜索一个比基准值大的元素搜索到即停止并记录指针的位置交换当前左边指针位置和右边指针位置的元素重复2,3,4步骤直到左边指针的值大于右边指针的值停止。 快速排序代码实现
//排序代码
public class Quick {public static void sort(Comparable[] a) {int lo 0;int hi a.length - 1;sort(a, lo,hi);}private static void sort(Comparable[] a, int lo, int hi) {if (hilo){return;}//对a数组中从lo到hi的元素进行切分int partition partition(a, lo, hi);//对左边分组中的元素进行排序//对右边分组中的元素进行排序sort(a,lo,partition-1);sort(a,partition1,hi);}public static int partition(Comparable[] a, int lo, int hi) {Comparable keya[lo];//把最左边的元素当做基准值int leftlo;//定义一个左侧指针初始指向最左边的元素int righthi1;//定义一个右侧指针初始指向左右侧的元素下一个位置//进行切分while(true){//先从右往左扫描找到一个比基准值小的元素while(less(key,a[--right])){//循环停止证明找到了一个比基准值小的元素if (rightlo){break;//已经扫描到最左边了无需继续扫描}}//再从左往右扫描找一个比基准值大的元素while(less(a[left],key)){//循环停止证明找到了一个比基准值大的元素if (lefthi){break;//已经扫描到了最右边了无需继续扫描}}if (leftright){//扫描完了所有元素结束循环break;}else{//交换left和right索引处的元素exch(a,left,right);}}//交换最后rigth索引处和基准值所在的索引处的值exch(a,lo,right);return right;//right就是切分的界限}/*
数组元素i和j交换位置
*/private static void exch(Comparable[] a, int i, int j) {Comparable t a[i];a[i] a[j];a[j] t;}/*
比较v元素是否小于w元素
*/private static boolean less(Comparable v, Comparable w) {return v.compareTo(w) 0;}
}//测试代码
public class Test {public static void main(String[] args) throws Exception {Integer[] arr {6, 1, 2, 7, 9, 3, 4, 5, 8};Quick.sort(arr);System.out.println(Arrays.toString(arr));}
}快速排序和归并排序的区别
快速排序是另外一种分治的排序算法它将一个数组分成两个子数组将两部分独立的排序。快速排序和归并排序 是互补的归并排序将数组分成两个子数组分别排序并将有序的子数组归并从而将整个数组排序而快速排序的 方式则是当两个数组都有序时整个数组自然就有序了。在归并排序中一个数组被等分为两半归并调用发生在 处理整个数组之前在快速排序中切分数组的位置取决于数组的内容递归调用发生在处理整个数组之后。
快速排序时间复杂度分析
快速排序的一次切分从两头开始交替搜索直到left和right重合因此一次切分算法的时间复杂度为O(n),但整个 快速排序的时间复杂度和切分的次数相关。最优情况每一次切分选择的基准数字刚好将当前序列等分。
如果我们把数组的切分看做是一个树那么上图就是它的最优情况的图示共切分了logn次所以最优情况下快 速排序的时间复杂度为O(nlogn);最坏情况每一次切分选择的基准数字是当前序列中最大数或者最小数这使得每次切分都会有一个子组那么总 共就得切分n次所以最坏情况下快速排序的时间复杂度为O(n^2); 平均情况每一次切分选择的基准数字不是最大值和最小值也不是中值这种情况我们也可以用数学归纳法证 明快速排序的时间复杂度为O(nlogn),由于数学归纳法有很多数学相关的知识容易使我们混乱所以这里就不对 平均情况的时间复杂度做证明了。
排序的稳定性 稳定性的定义
数组arr中有若干元素其中A元素和B元素相等并且A元素在B元素前面如果使用某种排序算法排序后能够保 证A元素依然在B元素的前面可以说这个该算法是稳定的。 稳定性的意义
如果一组数据只需要一次排序则稳定性一般是没有意义的如果一组数据需要多次排序稳定性是有意义的。例 如要排序的内容是一组商品对象第一次排序按照价格由低到高排序第二次排序按照销量由高到低排序如果第 二次排序使用稳定性算法就可以使得相同销量的对象依旧保持着价格高低的顺序展现只有销量不同的对象才需 要重新排序。这样既可以保持第一次排序的原有意义而且可以减少系统开销。
第一次按照价格从低到高排序
商品名称价格销量三星Note9399921华为mate30499965华为p30599965Iphone 11689932
第二次按照销量进行从高到低排序
商品名称价格销量华为mate30499965华为p30599965Iphone 11689932三星Note9399921
**常见排序算法的稳定性 **冒泡排序只有当arr[i]arr[i1]的时候才会交换元素的位置而相等的时候并不交换位置所以冒泡排序是一种稳定排序 算法。选择排序:选择排序是给每个位置选择当前元素最小的,例如有数据{5(1)8 5(2) 2 9 },第一遍选择到的最小元素为2 所以5(1)会和2进行交换位置此时5(1)到了5(2)后面破坏了稳定性所以选择排序是一种不稳定的排序算法。插入排序比较是从有序序列的末尾开始也就是想要插入的元素和已经有序的最大者开始比起如果比它大则直接插入在其 后面否则一直往前找直到找到它该插入的位置。如果碰见一个和插入元素相等的那么把要插入的元素放在相等 元素的后面。所以相等元素的前后顺序没有改变从原无序序列出去的顺序就是排好序后的顺序所以插入排序 是稳定的。希尔排序希尔排序是按照不同步长对元素进行插入排序 ,虽然一次插入排序是稳定的不会改变相同元素的相对顺序但在不同的插入排序过程中相同的元素可能在各自的插入排序中移动最后其稳定性就会被打乱所以希尔排序是不 稳定的。归并排序归并排序在归并的过程中只有arr[i]arr[i1]的时候才会交换位置如果两个元素相等则不会交换位置所以它 并不会破坏稳定性归并排序是稳定的。快速排序快速排序需要一个基准值在基准值的右侧找一个比基准值小的元素在基准值的左侧找一个比基准值大的元素 然后交换这两个元素此时会破坏稳定性所以快速排序是一种不稳定的算法。
