数组的快排
快速排序思想：(时间复杂度：nO(log以2为底，n的对数))
① 在数组中随机找一个枢纽元素。（该枢纽元素用于做比较）
② 小于枢纽元素的，放在左半区，大于枢纽元素的，放在右半区
对左半区继续进行①②，对右半区继续进行①②
示例：
给定一数组： 对于整体数组来说，我们选择第一个元素作为枢纽元素。记作tag
通过判断left、right所指向的数据：
如果left所指的数据，大于tag。即array[left] > tag，我们将left所指的数据，放在right位置上，如果left所指数据小于tag，则一直让left++。直到找到array[left] > tag为止。
如果right所指的数据，小于tag，即array[right] < tag，我们将right所指的数据，放在left位置上，反之一直right—，直到找到array[right] < tag为止。
当我们的left == right时，我们让这个位置上的元素变为 tag。
一次划分的过程：
① 判断right所指向的值 是否小于tag。 如图。array[right] == 30 < tag，所以我们让array[left] = 30；
② 然后判断left所指向的值，是否大于tag，如果不大于，则让left++，直到找到为止。如图，直到left指向89时，我们的array[left]==89 > tag，然后将left所指向的值，赋给array[right]
③ 再次移动right和left。重复①② 过程。
我们再次判断right所指向的值 是否小于tag，如果不小，则一直让right—，直到找到为止。如图，
当right指向45时,array[right] < tag。于是，right所指向的值 赋给 array[left]。
④ 再去判断，left所指向的值，是否大于tag，如果没找到， 则让left++，如图，当left指向100时，array[left]==100 > tag，于是left所指的值，赋给array[right]
⑤ 继续判断 right，right所指向的值是否小于tag，由上图得，array[right] == 100 > tag。所以让right—，此时left指向同一个元素。
这个时候，我们就不用再循环了，将tag赋给array[left]。这个时候，我们就发现，left之前的数据都是小于tag的，left之后的数据，都是大于tag的。
于是，我们就分左半部分和右半部分。左半部分和右半部分的排序和①②③④一样。
一次划分过程的代码实现：
选择数组第一个元素为基准元素时，就要从数组的右边开始比较。不能从左边开始比较。
// 一次划分的函数public static int parition(int[]br,int left,int right){int i = left; // 划分的起始位置int j = right; // 划分的终止位置int tag = br[i]; // 基数while(i<j){while(i<j && br[j] >tag) j--;if(i<j) br[i] = br[j];while(i<j && br[i]< tag) i++;if (i<j) br[j] = br[i];}br[i] = tag;return i;}
不断划分的过程：
public static void quickSort(int[] br){quickPass(br,0,br.length-1);}// 不断划分的过程public static void quickPass(int[]br,int left,int right){//如果left==right，意味着数据区域只有一个元素// 只有一个数据，我们就不需要划分了。if(left < right){int pos = parition(br,left,right);quickPass(br,left,pos-1);quickPass(br,pos+1,right);}}
最终实现：
public static void quickSort(int arr[]){quickPass(arr,0,arr.length-1);}
随机划分：
// 随机划分public int randomPartition(int[] arr,int left,int right){Random random = new Random();int index = random.nextInt((right-left+1))+left;int tmp = arr[index];arr[index] = arr[left];arr[left] = tmp;return partition(arr,left,right);}
注意随机划分时，index的取值。为什么要加一个left呢？
我们来想想，当进行第一次划分后，数组被分为两段，前半段是比tag小的数，后半段是比tag大的数。
此时，我们要对这两段再进行划分
对于后半段来说，我们假设 left = 5， right = 8.
如果没有+left的操作的话，我们计算下来的index = 3。但是！ 后半段第一个数据的索引是从5开始的。
我们计算出来的4，并不存在该范围。这就说明，4不是我们的绝对物理下标，我们需要+left 获取到绝对物理下标。
快排的非递归实现：
// 非递归实现快排public void niceQuickPass(int[] arr,int left,int right){Queue<Integer> queue = new LinkedList<>();if (left>=right) return;queue.offer(left);queue.offer(right);while(!queue.isEmpty()){left = queue.poll();right = queue.poll();int pos = partition(arr,left,right);if (left < pos-1){queue.offer(left);queue.offer(pos-1);}if (right > pos+1){queue.offer(pos+1);queue.offer(right);}}}
上述，我们使用的是两个指针，从两边向中间 逼近。即上述我们是以两个指针，分别从前面和后面查找
从前面查找的是比我们基准元素大的元素，把它们放在后面。
从后面查找的是比我们基准元素小的元素，把它们放在前面。
我们能不能从一个方向开始划分呢，即能不能两个指针同时从前面出发，将比基准大的元素放在后面，比基准小的元素放在前面？
思路：
① 定义两个指针：i，j，基准元素记作：tag
② i指向第一个元素，j指向第二个元素
③ 若arr[j] > tag，让j++
④ 若arr[j] <= tag，则让i++，交换i位置上和j位置上的值。
⑤ 重复③④ 直到 j>right 为止。 j>right了 就说明已经将整个数组划分完了。
图示：
① 定义两个指针 i,j，分别指向第一个元素和第二个元素
② 比较arr[j] > tag 。如上图所示，arr[j] == 90 >tag，于是j++，得到下图
③ 再比较arr[j] > tag。如上图所示，arr[j] == 88 > tag。让j++，得到下图：
④ 再比较arr[j] > tag。如上图所示，arr[j] == 15 < tag。于是先让i+1，然后交换i和j位置上的值，交换完后如下图所示：
⑤ 再比较arr[j] > tag。如上图所示,arr[j] == 90 >tag。让j++。得到下图：
⑥ 再比较arr[j] > tag。如上图所示，arr[j]==32 
⑦ 再比较arr[j]>tag。如上图所示，arr[j] == 88 >tag。于是让j++。得到下图：
⑧ 再比较arr[j]>tag。如上图所示，arr[j] == 23 < tag。于是先让i+1，再交换i和j位置上的值。
⑨ 再比较arr[j] > tag。如上图所示，arr[j] ==90 > tag。于是j++。得下图：
⑩ 再比较arr[j] > tag。如上图所示：arr[j] == 99 > tag，于是j++。得下图：
11.再比较arr[j] > tag。如上图所示,arr[j] == 47 < tag**。于是让i+1，交换i和j位置上的值。**<br /> <br /> 再比较arr[j] > tag。如上图所示，arr[j] == 88 > tag。让j++，**此时j已经超过了right的范围。此时划分结束。将i位置和left位置上的值进行交换，得下图：**<br /><br />**此时我们发现，在i的右边都是比tag小的数，在i的左边都是比tag大的数。此时一次划分的过程就结束了。**<br />**剩下的步骤 和 上面的双向划分是一样的。**
单链表的快速排序
单链表的快速排序，就是采用的是类似于数组的 单向划分的方法。
代码实现：（多次划分使用递归）
// 单链表的一次划分过程public ListNode partition(ListNode left,ListNode right){ListNode ip = left; //相当于iListNode jp = ip.next;// 相当于jint tag = ip.data;// 相当于arr[i]while(jp!=right){if(jp.data <= tag){ip = ip.next;change(ip,jp);}jp = jp.next;}change(left,ip);return ip;}private void change(ListNode ip,ListNode jp){int tmp = ip.data;ip.data = jp.data;jp.data = tmp;}// 单链表的多次划分public void quickPass(ListNode left,ListNode right){if (left!=right){ListNode p = partition(left,right);quickPass(left,p);quickPass(p.next,right);}}public void quickSort2(){quickPass(head,null);}
多次划分不使用递归：
// 单链表的多次划分(非递归)
public void niceQuickPass(ListNode left,ListNode right){
Queue<ListNode> queue = new LinkedList();
queue.offer(left);
queue.offer(null);
while(!queue.isEmpty()){
left = queue.poll();
right = queue.poll();
ListNode p = partition(left,right);
if (left!=p){
queue.offer(left);
queue.offer(p);
}
if (p.next!=right){
queue.offer(p.next);
queue.offer(right);
}
}
}
public void niceQuickSort(){
niceQuickPass(head,null);
}
若有收获，就点个赞吧
0 人点赞
