快速排序算法

快速排序算法

思想(从小到大排序)

  • 快速排序是使用分治法来完成的
  • 基本思想就是先从其中选取一个基准值,然后从数组的两端开始移动查找,在右边移动查找到比基准值小的数据停止移动,此时在左边查找到比基准值大的数据也停止查找,交换这两个查找到的数据,交换完成之后两端继续移动查找,如果左边找到比基准值大的,右边找到比基准值小的数据,再次交换。直到查找到同一个数据上(相遇)或者”擦肩而过”。那么将基准值相遇的那个值交换,此时就能够保证在基准值左边的都是比基准值小的,在其右边的都是比其大的数,此时一轮查找结束。接下来这个基准值将一个数组分成了两半,左边的是小的,右边是大的,那么我们再分别对左边和右边的数据进行相同的操作,直至不可拆分成新的子序列为止。
  • 快速排序的最坏运行时间是O(n2),但期望的运行时间是O(nlgn)
  • 测试

123456

int[] array={ 9,7,4,67,45,2,24,33,22,45,88,12,1,0,25};quickSort(array, 0, array.length-1);for (int i = 0; i < array.length; i++) { System.out.print(array[i]+"\t");}

另外一种方式

选取数组的第一个数为基准值

  • 我们选取数组的第一个元素作为基准值
  • 此时先从数组的最右边开始查找,如果找到比基准值小的停止查找,再从最左边开始查找,直至找到比基准值大的,那么两边就交换,交换完成之后,最右边再次开始查找,找到就等待左边找到数交换,直至双方相遇。那么把相遇的那个点的数据和基准值交换即可,那么现在在基准值左边的都是小的,在右边的都是大的,此时的基准值将数组分成了两个子序列,再对子序列进行重复的操作,直到不可拆分成子序列。
  • 实现的代码
public static void quickSort(int[] arr,int low,int high){
	        
	        //递归结束的条件,如果此时的子序列只有一个元素就是low=high,就不用排序了
	        if(low>=high){
	            return;
	        }
	        
	        int i=low;   //i从最左边开始查找
	        int j=high;   //i从最右边开始查找
	        int temp = arr[low]; //设置基准值为第一个元素,temp
	        
	        //如果此时的i和j没有相遇,一直进行下去
	        while (i<j) {
	        	//先从右边开始查找,如果没有找到比基准值小的并且没有相遇,那么继续向右查找
	            while (temp<=arr[j]&&i<j) {
	                j--;   //向左移动
	            }
	            
	            //再从左边开始查找,如果没有找到比基准值大的并且没有相遇,那么继续向左查找
	            while (temp>=arr[i]&&i<j) {
	                i++;   // 向右移动
	            }
	           
	           //代码能够运行到这里,那么表示已经找到了右面小于基准值的,左面大于基准值的,那么就可以交换数据了
	           //这里的i<j用于控制在最后相遇的时候还要交换数据,不必交换了,可以省去一次的交换
	          if (i<j) {
	        	  	//交换数据
	        	   	int t = arr[j];
	                arr[j] = arr[i];
	                arr[i] = t;
	          }
	             

	        }
	        
	        //最后将基准为与i和j相等位置的数字交换
	         arr[low] = arr[i];  //第一个元素设置为i和j相遇的那个值
	         arr[i] = temp;   //相遇的那个地方设置为基准值
	         
	        //递归调用左半数组,以基准值为中心切割
	        quickSort(arr, low, j-1);
	        //递归调用右半数组
	        quickSort(arr, j+1, high);
	    }
  • 测试
int[] array={ 9,7,4,67,45,2,24,33,22,45,88,12,1,0,25};
quickSort(array, 0, array.length-1);

for (int i = 0; i < array.length; i++) {
	System.out.print(array[i]+"\t");
}

另外一种方式

public static int partition(int[] array,int low,int high){
		  int i=low;
		  int j=high;
		  int temp=array[low];  //选取第一个为基准数
		  //如果此时的还没有相遇,表示没有结束
		  while(i<j){
			  //因为基准数是最左面的,因此从最右面开始查找
			  //当当前的值比基准值大,并且i和j不相等,即是没有相遇
			  while(temp<array[j]&&i<j){
				  j--;   //向左移动,继续查找
			  }
			  
			  //从左面开始查找,如果查找到的数据array[i]小于基准值并且i和j没有相遇,那么继续向右移动查找
			  while(array[i]<temp&&i<j){
				  i++;  //继续向右移动查找
			  }
			  
			//代码能够运行到这里,那么表示已经找到了右面小于基准值的,左面大于基准值的,那么就可以交换数据了
	          if (i<j) {
	        	   	int t = array[j];
	                array[j] = array[i];
	                array[i] = t;
	          }
		  }
		  
		  low=i;
		  high=j;
		  
		  return j ;   //返回当前的基准值在数组中的索引,用于分割子序列
	 }

	 
	 public static void quickSort1(int[] arrary,int low,int high){
		 //停止条件,如果low>high表示相遇,那么停止递归
		 if(low>high){
			 return;
		 }
		 int index=partition(arrary, low, high);  //获取基准值的位置
		 quickSort1(arrary, low, index-1);   //左边的
		 quickSort1(arrary,index+1,high);  //右边的
		 
	 }

为什么从最右边开始查找

  • 如果从最左边开始查找,那么有可能某一次查找到了比基准值大的数,停止查找,等待最右边查找到比基准值小的数,但是此时最右边一直在查找,直到和其相遇都没有查找到比基准值小的数据,那么此时的的基准值就需要和这个比它还大的值交换,那么出现的结果就是此时的数组的第一个数是比基准值大的,违背了左边都是比基准值小的,右边都是比基准值大的。
  • 如果从最右边开始查找,即使当某一个时刻查找到了比基准值小的数据,停止查找,等待左边查找到比基准值大的数据。但是左边没有找到,直至相遇,那么此时相遇的这个数任然是比基准值小的,因此和基准值交换是没有问题的

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏开发与安全

算法:快速排序以及第k小元素的线性选择算法

简要介绍下快速排序的思想:通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行...

22910
来自专栏趣谈编程

归并排序

面试官: 聊聊归并排序 归并排序是建立在归并操作的一种高效的排序方法,该方法采用了分治的思想,比较适用于处理较大规模的数据,但比较耗内存,今天我们聊聊归并排序 ...

4137
来自专栏前端儿

苹果

ctest有n个苹果,要将它放入容量为v的背包。给出第i个苹果的大小和价钱,求出能放入背包的苹果的总价钱最大值。

1002
来自专栏算法channel

其他|二维指针,数组指针,指针数组

望时间的流逝不仅仅丰富了我们的阅历,更重要的是通过提炼让我们得以升华,走向卓越。 1c++ c/c++的重要性毋庸置疑,凡是对性能要求很高的系统和算法,其中核...

3085
来自专栏LeetCode

LeetCode <dp>64. Minimum Path Sum

Given a m x n grid filled with non-negative numbers, find a path from top left t...

1610
来自专栏C语言C++游戏编程

C语言内置运算符丰富到令人头皮发麻,C语言基础教程之运算符篇

运算符是告诉编译器执行特定数学或逻辑函数的符号。C语言内置运算符丰富,并提供以下类型的运算符 -

1231
来自专栏醒者呆

融会贯通——最常用的面向对象设计原则“合成复用原则”

复用一个类的时候,多使用对象的组合/聚合的关联关系,而不是继承。 之前提到的“依赖倒转原则”,是以里氏代换原则为基础的实现开闭原则目标的手段,这一条路线涉及到的...

2928
来自专栏学习力

《Java从入门到放弃》JavaSE入门篇:运算符

1636
来自专栏申龙斌的程序人生

零基础学编程028:面向对象编程OOP

在《零基础学编程021:获取股票实时行情数据》一节中,我们想获取6支股票的行情数据,在《零基础学编程022:函数的世界》里我们能够把重复性的代码封装为一个函数p...

3076
来自专栏青青天空树

成绩大排队

其中姓名和学号均为不超过10个字符的字符串,成绩为0到100之间的一个整数,这里保证在一组测试用例中没有两个学生的成绩是相同的。

822

扫码关注云+社区

领取腾讯云代金券