交換排序之快速排序（Java）
博客說明
文章所涉及的資料來自互聯網整理和個人總結，意在于個人學習和經驗匯總，如有什么地方侵權，請聯系本人洗掉，謝謝！
快速排序法介紹
快速排序（Quicksort）是對冒泡排序的一種改進，基本思想是：通過一趟排序將要排序的資料分割成獨立的兩部分，其中一部分的所有資料都比另外一部分的所有資料都要小，然后再按此方法對這兩部分資料分別進行快速排序，整個排序程序可以遞回進行，以此達到整個資料變成有序序列
代碼
package cn.guizimo.sort;
import java.util.Arrays;
public class QuickSort {
public static void main(String[] args) {
int[] arr = {-9, 78, 0, 23, -587, 71};
System.out.println("排序前");
System.out.println(Arrays.toString(arr));
quickSort(arr, 0, arr.length - 1);
System.out.println("排序后");
System.out.println(Arrays.toString(arr));
}
public static void quickSort(int[] arr, int left, int right) {
int l = left;
int r = right;
int temp = 0;
int pivot = arr[(left + right) / 2];
while (l < r) {
while (arr[l] < pivot) {
l += 1;
}
while (arr[r] > pivot) {
r -= 1;
}
if (l >= r) {
break;
}
temp = arr[l];
arr[l] = arr[r];
arr[r] = temp;
if (arr[l] == pivot) {
r -= 1;
}
if (arr[r] == pivot) {
l += 1;
}
}
if (l == r) {
l += 1;
r -= 1;
}
//向左遞回
if (left < r) {
quickSort(arr, left, r);
}
//向右遞回
if (right > l) {
quickSort(arr, l, right);
}
}
}
測驗
測驗速度
package cn.guizimo.sort;
import java.util.Arrays;
public class QuickSort {
public static void main(String[] args) {
int max = 80000;
int[] arr = new int[max];
for (int i = 0; i < max; i++) {
arr[i] = (int)(Math.random() * 8000000);
}
long date1 = System.currentTimeMillis();
quickSort(arr, 0, arr.length - 1);
long date2 = System.currentTimeMillis();
System.out.println("快速排序"+max+"陣列的時間為："+(date2-date1));
}
public static void quickSort(int[] arr, int left, int right) {
int l = left;
int r = right;
int temp = 0;
int pivot = arr[(left + right) / 2];
while (l < r) {
while (arr[l] < pivot) {
l += 1;
}
while (arr[r] > pivot) {
r -= 1;
}
if (l >= r) {
break;
}
temp = arr[l];
arr[l] = arr[r];
arr[r] = temp;
if (arr[l] == pivot) {
r -= 1;
}
if (arr[r] == pivot) {
l += 1;
}
}
if (l == r) {
l += 1;
r -= 1;
}
//向左遞回
if (left < r) {
quickSort(arr, left, r);
}
//向右遞回
if (right > l) {
quickSort(arr, l, right);
}
}
}
感謝
尚硅谷
萬能的網路
以及勤勞的自己
關注公眾號： 歸子莫，獲取更多的資料，還有更長的學習計劃
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/156472.html
標籤：Java
上一篇：Halo 開源專案使用jsdelivr進行CDN加速.
下一篇：學習Java的Day03