目录

前言快速排序算法简介快排算法实现1、快排原理（简述）2、java代码实现3、代码优化3、测试结果(经过多次测试，取了中间值)

前言

算法真好玩，今天写写快排

快速排序算法简介

快速排序作为常见的一种排序，可以说关于他的介绍已经烂大街了。本文不做赘述。 值得一提的是

快速排序是冒泡排序的改良版他的时间复杂度也为O(nlogn)。快速排序也属于稳定排序，即排序之后，相等的两个元素的相对位置不会发生改变经过测试快排的排序效率相当高，这也是他流行的原因吧。百度百科评价其为排序一哥。这个咱也不知道是不是，不敢乱说。

快排算法实现

1、快排原理（简述）

（1）首先，第一次排序时，一般把第一个元素作为要排序的基准元素。要达到的效果是，这一次排序完成之后这个元素放在了他该在的位置上。而他的左边全是比它大的数，他的右边全是比他小的数。 （2.1）为了实现这一效果，我们采用下面的方法：先把基准元素保存在一个变量中，定义一个头指针指向基准元素所在位置（因为他是第一个。且因为基准变量已经被保存起来，这时这个位置可以当成是空的），尾指针指向最后一个位置。尾指针先开始向前遍历，遇到比基准元素小的，就把这个值赋值给头指针所在位置的元素（前面说过，可以把这个位置当成空的，所以这个赋值操作就合理了。相应的尾指针所在的值已经被使用了，这时可以认为尾指针所在的地方是空的了）。接着尾指针停驻，换成头指针开始向后遍历。遇到比基准元素大的，就把这个值赋值给尾指针所在位置的元素（道理和前面的一样）。接着头指针停驻，尾指针遍历，如此循环。 （2.2）直到头尾指针相遇，这时，比基准元素大的都放到了首尾指针的后面，比基准元素小的都放到了首尾指针的前面（经过前面的操作确实可以做到，好好想想）。那么首尾指针此时所在位置就是基准元素他应该在的地方。。。 （3）基准元素的位置定好了，我们用二分思想把他左边和右边分成两个部分。递归调用上面的方法，就可以使所有元素都放到他该呆的地方了。

本人不喜欢长篇大论，想尽可能用简洁的语言说明一下。突然发现这东西真不是简简单单就能说明白的🤔🤔🤔。建议结合代码和动图理解。动图自己去网上找找很多的。

2、java代码实现

给出个人的代码实现

public int[] quicksort1(int []a){ if(a.length==0)return a; if(a.length<3){//只剩1个元素或者两个元素，递归结束 if(a[0]>a[a.length-1]){//两个元素时。对这两个元素排序 int tmp=a[0]; a[0]=a[a.length-1]; a[a.length-1]=tmp; } return a; } int tmp=a[0];//当前标准元素,相当于在头指针位置挖了个坑 int head=0;//头指针 int tail=a.length-1;//尾指针 boolean b=false;//当b为false时，尾指针向前遍历。当b为true时，尾指针向后遍历 while(head!=tail){//当头尾指针没有相遇时 if(!b) {//尾指针向前遍历 if (a[tail] < tmp) {//尾指针指向的元素比标准元素小，把尾指针元素填到头指针的坑里。尾指针成为新的坑 a[head++] = a[tail]; b=true;//改变遍历方向 } else { tail--; } }else {//头指针向后遍历 if(a[head]>tmp){ a[tail--]=a[head]; b=false; }else{ head++; } } } //当循环结束，head和tail所在位置就是本轮标准元素该在的位置 a[head]=tmp;//得到标准元素排序后的准确位置 int[] right = Arrays.copyOfRange(a,0,head); int[] left =Arrays.copyOfRange(a,head+1,a.length); left=quicksort1(left); right=quicksort1(right); for (int i = 0; i <right.length ; i++) { a[i]=right[i]; } for (int i = 0; i <left.length ; i++) { a[i+head+1]=left[i]; } return a; }

3、代码优化

代码写完了，突然想去看看别人的代码。不看不要紧，一看吓一跳，怎么别人的代码辣么少。经过分析，上面的代码创建好了几个新数组，浪费空间不说还没有节省时间。于是修改代码如下

public int[] quicksort2(int []a,int head,int tail){ if(tail-head<2){//优化递归结束条件 return a; } int tmp=a[head]; int h=head;//备份起始下标 int t=tail;//备份结束下标 boolean b=false;//当b为false时，尾指针向前遍历。当b为true时，头指针向后遍历 while(head!=tail){//当头尾指针没有相遇时 if(!b) {//尾指针向前遍历 if (a[tail] < tmp) {//尾指针指向的元素比标准元素小，把尾指针元素填到头指针的坑里。尾指针成为新的坑 a[head++] = a[tail]; b=true;//改变遍历方向 } else { tail--; } }else {//头指针向后遍历 if(a[head]>tmp){ a[tail--]=a[head]; b=false; }else{ head++; } } } a[head]=tmp; quicksort2(a,h,head-1);//优化内存占用 quicksort2(a,head+1,t); return a; }

这回看着舒服点了

3、测试结果(经过多次测试，取了中间值)

原数组{3,44,38,5,47,15,36,26,27,2,46,4,19,50,48,38}

QuickSort1排序时间为：49100 [2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 38, 44, 46, 47, 48, 50]

QuickSort2排序时间为：31800 [2, 3, 4, 5, 15, 19, 27, 26, 36, 38, 38, 44, 46, 47, 48, 50]

试了好几次，优化之后的代码执行确实变快了