快速排序相當(dāng)于冒泡排序的進(jìn)化版本，優(yōu)點(diǎn)是速度比冒泡排序更快，缺點(diǎn)是寫起來邏輯比冒泡排序啰嗦一點(diǎn)，沒那么直觀。

快速排序之所以比較快，是因為相比冒泡排序，每次交換是跳躍式的。每次排序的時候 設(shè)置一個基準(zhǔn)點(diǎn)，將小于等于基準(zhǔn)點(diǎn)的數(shù)全部放到基準(zhǔn)點(diǎn)的左邊，將大于等于基準(zhǔn)點(diǎn)的數(shù)全 部放到基準(zhǔn)點(diǎn)的右邊。這樣在每次交換的時候就不會像冒泡排序一樣只能在相鄰的數(shù)之間進(jìn) 行交換，交換的距離就大得多了。因此總的比較和交換次數(shù)就少了，速度自然就提高了。當(dāng) 然在最壞的情況下，仍可能是相鄰的兩個數(shù)進(jìn)行了交換。因此快速排序的最差時間復(fù)雜度和 冒泡排序是一樣的，都是 O(N2)，它的平均時間復(fù)雜度為 O (NlogN)

下圖是對:6 1 2 7 9 3 4 5 10 8進(jìn)行快速排序的描述圖

題目:

輸入一串沒有順序的數(shù)字，對這串?dāng)?shù)字進(jìn)行升序排序，并輸出

package _4_9_test;

import java.util.ArrayList;

import java.util.Scanner;

/*快速排序法

*

* */

public class EightyEight {

public static void main(String[] args) {

Scanner scanner = new Scanner(System.in);

int n = scanner.nextInt();

int num[] = new int[n];

for (int i = 0; i < n; i++) {

num[i] = scanner.nextInt();

}

quitSort(num, 0, n - 1);

for (int i : num) {

System.out.print(i + " ");

}

}

public static void quitSort(int num[], int getLeft, int getRight) {

int left, right, t;

// 左右起始的位置

left = getLeft;

right = getRight;

// 如果左右的位置發(fā)生了交錯，說明當(dāng)前序列的循環(huán)結(jié)束了

if (left > right) {

return;

}

// 用于存放基準(zhǔn)位

int temp;

// 選擇序列的第一個數(shù)作為基準(zhǔn)位

temp = num[left];

// 當(dāng)左右位置還沒碰面時

while (left < right) {

// 從序列的右邊往左走，如果數(shù)字大于基準(zhǔn)位，則繼續(xù)走，直到碰到小于基準(zhǔn)位的數(shù)字

while (left < right && temp <= num[right]) {

right--;

}

// 從序列的左邊往右走，如果數(shù)字小于基準(zhǔn)位，則繼續(xù)走，直到碰到大于基準(zhǔn)位的數(shù)字

while (left < right && temp >= num[left]) {

left++;

}

// 將左邊大于基準(zhǔn)位的數(shù)和右邊小于基準(zhǔn)位的數(shù)進(jìn)行位置互換

t = num[right];

num[right] = num[left];

num[left] = t;

}

if (left >= right) {

// 序列中數(shù)字位置對調(diào)結(jié)束后，將基準(zhǔn)位歸位

num[getLeft] = num[left];

num[left] = temp;

}

// 遞歸

// 對基準(zhǔn)位左邊的序列重復(fù)執(zhí)行上面的步驟

quitSort(num, getLeft, left - 1);

// 對基準(zhǔn)位右邊的序列重復(fù)執(zhí)行上面的步驟

quitSort(num, left + 1, getRight);

}

}

總結(jié)

以上是生活随笔為你收集整理的java里面快速排序_Java:快速排序的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。