快速排序
快速排序法介绍:
快速排序（Quicksort）是对冒泡排序的一种改进。基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列
快速排序法示意图:
- 快速排序法应用实例:
要求: 对 [-9,78,0,23,-567,70] 进行从小到大的排序，要求使用快速排序法。【测试 8w 和 800w】说明[验证分析]:
1) 如果取消左右递归，结果是 -9 -567 0 23 78 70
2) 如果取消右递归,结果是 -567 -9 0 23 78 70
3) 如果取消左递归,结果是 -9 -567 0 23 70 78
代码实现
java;gutter:true;
package com.xuge.sort;</p>
<p>import java.util.Arrays;</p>
<p>/<strong>
* author: yjx
* Date :2022/5/3020:39
</strong>/
public class QuickSort {
public static void main(String[] args) {
int arr[] = {1, -1, 90, 29, 67, 28};
quickSort(arr, 0, arr.length - 1);
System.out.println(Arrays.toString(arr));
}</p>
<p>/*<em>
* @param arr 数组
* @param left 左边索引
* @param right 右边索引
</em>/
public static void quickSort(int[] arr, int left, int right) {
int l = left;
int r = right;
int pivot = arr[(left + right) / 2];
int temp = 0;
//比pivot索引的值大-右 小-左
while (l < r) {
//在左边一直找，找到大于等于pivot值,才退出
while (arr[l] < pivot) {
l += 1;
}
//在右边一直找，找到小于等于pivot值,才退出
while (arr[r] > pivot) {
r -= 1;
}
//说明pivot左右两边的值都是按造左边小于，右边大于
if (l >= r) {
break;
}
//交换
temp = arr[l];
arr[l] = arr[r];
arr[r] = temp;
//交换完之后，如果发现arr[l]==pivot 相等 r-- 前移
if (arr[l] == pivot) {
r -= 1;
}
//交换完之后，如果发现arr[r]==pivot 相等 l++ 后移
if (arr[r] == pivot) {
l += 1;
}</p>
<pre><code>}
//如果l=r;必须l++,r--,否则出现栈溢出
if(l==r){
l+=1;
r-=1;
}
//向左递归
if(leftl){
quickSort(arr, l, right);
}
</code></pre>
<p>}
}</p>
<pre><code>
### 速度测试
;gutter:true;
public static void main(String[] args) {
// int arr[] = {1, -1, 90, 29, 67, 28};
// quickSort(arr, 0, arr.length – 1);
// System.out.println(Arrays.toString(arr));
int arr2[] = new int[80000];
for (int i = 0; i < 80000; i++) {
arr2[i] = (int) (Math.random() * 80000000);//生成随机数[0,80000000);
}
System.out.println("====输出数组=====");
Date data = new Date();
SimpleDateFormat sdf = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss");
String str = sdf.format(data);
System.out.println("排序前的时间是:" + str);//23
quickSort(arr2,0,arr2.length-1);
Date data2 = new Date();
String str2 = sdf.format(data2);
System.out.println("排序后的时间是" + str2);//25
}
Original: https://www.cnblogs.com/XugeA/p/16328257.html
Author: xugeA
Title: 排序算法-快速排序
原创文章受到原创版权保护。转载请注明出处：https://www.johngo689.com/605019/
转载文章受原作者版权保护。转载请注明原作者出处！