排序算法——快速排序

avatar 2017年10月11日12:27:24 5 2893 views
博主分享免费Java教学视频，B站账号：Java刘哥 ，长期提供技术问题解决、项目定制：本站商品点此
快速排序由于排序效率在同为O(N*logN)的几种排序方法中效率较高，因此经常被采用，再加上快速排序思想----分治法也确实实用，因此很多软件公司的笔试面试，包括像腾讯，微软等知名IT公司都喜欢考这个，还有大大小的程序方面的考试如软考，考研中也常常出现快速排序的身影。



总的说来，要直接默写出快速排序还是有一定难度的，因为本人就自己的理解对快速排序作了下白话解释，希望对大家理解有帮助，达到快速排序，快速搞定。



快速排序是C.R.A.Hoare于1962年提出的一种划分交换排序。它采用了一种分治的策略，通常称其为分治法(Divide-and-ConquerMethod)。

该方法的基本思想是：
1．先从数列中取出一个数作为基准数。

2．分区过程，将比这个数大的数全放到它的右边，小于或等于它的数全放到它的左边。

3．再对左右区间重复第二步，直到各区间只有一个数。



下面上个霸气的图来描述下整个算法的处理过程。





这是为什么呢？

快速排序之所比较快，因为相比冒泡排序，每次交换是跳跃式的。每次排序的时候设置一个基准点，将小于等于基准点的数全部放到基准点的左边，将大于等于基准点的数全部放到基准点的右边。这样在每次交换的时候就不会像冒泡排序一样每次只能在相邻的数之间进行交换，交换的距离就大的多了。因此总的比较和交换次数就少了，速度自然就提高了。当然在最坏的情况下，仍可能是相邻的两个数进行了交换。因此快速排序的最差时间复杂度和冒泡排序是一样的都是O(N2)，它的平均时间复杂度为O(NlogN)。其实快速排序是基于一种叫做“二分”的思想。我们后面还会遇到“二分”思想，到时候再聊。

以上内容来自：

白话经典算法系列之六 快速排序 快速搞定

坐在马桶上看算法：快速排序



由于他的代码似乎有点问题，这里又写了一个代码
  1. package algorithm;
  3. public class Sort_quick {
  4.     //打印数组
  5.     public static void printArr(int[] arr) {
  6.         for (int i:arr)
  7.             System.out.print(i+" ");
  8.         System.out.println();
  9.     }
  11.     //获得基准位的位置
  12.     public static int partition(int []arr,int left,int right){
  13.         //固定的切分方式
  14.         int key=arr[left],temp;
  15.         while(left<right){//两个哨兵相遇则停止
  16.             while(left<right&&arr[right]>=key){//从右边开始找,找一个小于基准数的,找到则停止
  17.                 right--;
  18.             }
  19.             arr[left]=arr[right];
  20.             while(left<right&&arr[left]<=key){//从左边开始找,找一个大于基准数的，找到则停止
  21.                 left++;
  22.             }
  23.             arr[right]=arr[left];
  24.         }
  25.         //这时候arr[left]和arr[right]很可能相等,且还差key的值没排进去
  26.         arr[right]=key;
  27.         //打印每一轮排序的结果
  28.         printArr(arr);
  29.         return right;
  30.     }
  32.     public static void quickSort(int[] arr,int left ,int right){
  33.         if(left>=right){
  34.             return ;
  35.         }
  36.         int index=partition(arr,left,right);
  37.         quickSort(arr,left,index-1);
  38.         quickSort(arr,index+1,right);
  39.     }
  42.     public static void main(String args[]) {
  43.         int[] arr = {6,1,2,7,9,3,4,5,10,8};
  44.         quickSort(arr,0,arr.length-1);
  45.     }
  46. }

历史上的今天
十月
11日
  • 微信
  • 交流学习，资料分享
  • weinxin
  • 个人淘宝
  • 店铺名：言曌博客咨询部

  • (部分商品未及时上架淘宝)
avatar

发表评论

avatar 登录者：匿名
匿名评论，评论回复后会有邮件通知

  

已通过评论：0   待审核评论数：0