快速排序遞歸java

① 請問java快速排序法是怎麼算的

* 步驟為： * 1. 從數列中挑出一個元素，稱為 "基準"（pivot）， * 2. 重新排序數列，所有元素比基準值小的擺放在基準前面，所有元素比基準值大的擺在基準的後面（相同的數可以到任一邊）。在這個分割之後，該基準是它的最後位置。這個稱為分割（partition）操作。 * 3. 遞歸地（recursive）把小於基準值元素的子數列和大於基準值元素的子數列排序。 * 遞回的最底部情形，是數列的大小是零或一，也就是永遠都已經被排序好了。 * @param data 待排序的數組 * @param low * @param high * @see SortTest#qsort(int[], int, int) * @see SortTest#qsort_desc(int[], int, int) */ public void quickSort(int[] data, String sortType) { if (sortType.equals("asc")) { //正排序，從小排到大 qsort_asc(data, 0, data.length - 1); } else if (sortType.equals("desc")) { //倒排序，從大排到小 qsort_desc(data, 0, data.length - 1); } else { System.out.println("您輸入的排序類型錯誤！"); } } /** * 快速排序的具體實現，排正序 * @param data * @param low * @param high */ private void qsort_asc(int data[], int low, int high) { int i, j, x; if (low < high) { //這個條件用來結束遞歸 i = low; j = high; x = data[i]; while (i < j) { while (i < j && data[j] > x) { j--; //從右向左找第一個小於x的數 } if (i < j) { data[i] = data[j]; i++; } while (i < j && data[i] < x) { i++; //從左向右找第一個大於x的數 } if (i < j) { data[j] = data[i]; j--; } } data[i] = x; qsort_asc(data, low, i - 1); qsort_asc(data, i + 1, high); } } /** * 快速排序的具體實現，排倒序 * @param data * @param low * @param high */ private void qsort_desc(int data[], int low, int high) { int i, j, x; if (low < high) { //這個條件用來結束遞歸 i = low; j = high; x = data[i]; while (i < j) { while (i < j && data[j] < x) { j--; //從右向左找第一個小於x的數 } if (i < j) { data[i] = data[j]; i++; } while (i < j && data[i] > x) { i++; //從左向右找第一個大於x的數 } if (i < j) { data[j] = data[i]; j--; } } data[i] = x; qsort_desc(data, low, i - 1); qsort_desc(data, i + 1, high); } }

② java中快速排序的實現思路

快速排序法：快速排序法號稱是目前最優秀的演算法之一，實現思路是，將一個數組的排序問題看成是兩個小數組的排序問題，而每個小的數組又可以繼續看成更小的兩個數組，一直遞歸下去，直到數組長度大小最大為2

③ 【java快速排序】大神們能看下我段代碼末尾第二個遞歸的參數要怎麼傳才對啊

最後一句的傳參應該是沒有問題的。明顯有問題的一個地方是，int pivot = arr[0]; ，需要排序的區域為 arr[start] 到 arr[end]，需要應該以 arr[start] 作為樞軸，int pivot = arr[start]

④ 排序都有哪幾種方法用JAVA實現一個快速排序。

排序的方法有：插入排序（直接插入排序、希爾排序），交換排序（冒泡排序、快速排序），選擇排序（直接選擇排序、堆排序），歸並排序，分配排序（箱排序、基數排序）
快速排序的偽代碼。
/ /使用快速排序方法對a[ 0 :n- 1 ]排序
從a[ 0 :n- 1 ]中選擇一個元素作為m i d d l e，該元素為支點
把餘下的元素分割為兩段left 和r i g h t，使得l e f t中的元素都小於等於支點，而right 中的元素都大於等於支點
遞歸地使用快速排序方法對left 進行排序
遞歸地使用快速排序方法對right 進行排序
所得結果為l e f t + m i d d l e + r i g h t

⑤ Java程序快速排序是怎樣的，舉個例子說明一下

publicclassQuickSort{
privatestaticvoidQuickSort(int[]array,intstart,intend){if(start<end){
intkey=array[start];//初始化保存基元
inti=start,j;//初始化i,j
for(j=start+1;j<=end;j++)
if(array[j]<key){//如果此處元素小於基元，則把此元素和i+1處元素交換，並將i加1，如大於或等於基元則繼續循環inttemp=array[j];
array[j]=array[i+1];
array[i+1]=temp;
i++;
}
}
array[start]=array[i];//交換i處元素和基元
array[i]=key;
QuickSort(array,start,i-1);//遞歸調用
QuickSort(array,i+1,end);
}
}
publicstaticvoidmain(String[]args){
int[]array=newint[]{11,213,134,44,77,78,23,43};
QuickSort(array,0,array.length-1);
for(inti=0;i<array.length;i++){
System.out.println((i+1)+"th:"+array[i]);
}
}
}

⑥ java中快速排序的演算法舉個例子

package person.test;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;
import java.util.Random;

/**
* class name: RapidSort
* description: Java快速排序法：數組和集合
* @author Jr
*
*/
public class RapidSort {
private Random ran = new Random(); // 聲明一個全局變數ran，用來隨機生成整數

/**
* method name: sortArray
* description: 對數組的快速排序，只能用於int[]類型的數組
* @return
*/
private void sortArray() {
int[] array = new int[10]; // 聲明數組長度為10
for (int i = 0 ; i < array.length; i++) {
array[i] = ran.nextInt(10) + 1; // 數組賦值
}
Arrays.sort(array);
System.out.println(Arrays.toString(array));
}

/**
* method name: sortList
* description: 對集合的快速排序，可以用於List<Object>類型數組，
* 隱含意思就是對所有類型數組都適用
* @return
*/
private void sortList() {
List<Integer> list = new ArrayList<Integer>();
for (int i = 0 ; i < 10; i++) {
list.add(ran.nextInt(10) + 1); // 給集合賦10個值
}
Collections.sort(list);
System.out.println(list);
}

public static void main(String[] args) {
RapidSort rs = new RapidSort();
rs.sortArray();
rs.sortList();
}
}

⑦ java怎麼實現排序

Java實現幾種常見排序方法

日常操作中常見的排序方法有：冒泡排序、快速排序、選擇排序、插入排序、希爾排序，甚至還有基數排序、雞尾酒排序、桶排序、鴿巢排序、歸並排序等。
以下常見演算法的定義
1. 插入排序：插入排序基本操作就是將一個數據插入到已經排好序的有序數據中，從而得到一個新的、個數加一的有序數據，演算法適用於少量數據的排序，時間復雜度為O(n^2)。是穩定的排序方法。插入排序的基本思想是：每步將一個待排序的紀錄，按其關鍵碼值的大小插入前面已經排序的文件中適當位置上，直到全部插入完為止。
2. 選擇排序：選擇排序（Selection sort）是一種簡單直觀的排序演算法。它的工作原理是每一次從待排序的數據元素中選出最小（或最大）的一個元素，存放在序列的起始位置，直到全部待排序的數據元素排完。 選擇排序是不穩定的排序方法。
3. 冒泡排序：冒泡排序（Bubble Sort），是一種計算機科學領域的較簡單的排序演算法。它重復地走訪過要排序的數列，一次比較兩個元素，如果他們的順序錯誤就把他們交換過來。走訪數列的工作是重復地進行直到沒有再需要交換，也就是說該數列已經排序完成。這個演算法的名字由來是因為越大的元素會經由交換慢慢「浮」到數列的頂端。
4. 快速排序：快速排序（Quicksort）是對冒泡排序的一種改進。它的基本思想是：通過一趟排序將要排序的數據分割成獨立的兩部分，其中一部分的所有數據都比另外一部分的所有數據都要小，然後再按此方法對這兩部分數據分別進行快速排序，整個排序過程可以遞歸進行，以此達到整個數據變成有序序列。
5. 歸並排序：歸並排序是建立在歸並操作上的一種有效的排序演算法,該演算法是採用分治法（Divide and Conquer）的一個非常典型的應用。將已有序的子序列合並，得到完全有序的序列；即先使每個子序列有序，再使子序列段間有序。若將兩個有序表合並成一個有序表，稱為二路歸並。
6. 希爾排序：希爾排序(Shell Sort)是插入排序的一種。也稱縮小增量排序，是直接插入排序演算法的一種更高效的改進版本。希爾排序是非穩定排序演算法。希爾排序是把記錄按下標的一定增量分組，對每組使用直接插入排序演算法排序；隨著增量逐漸減少，每組包含的關鍵詞越來越多，當增量減至1時，整個文件恰被分成一組，演算法便終止。
https://www.cnblogs.com/wangmingshun/p/5635292.html

⑧ 如何理解java數據結構中的快速排序方法

原理：

快速排序也是分治法思想的一種實現，他的思路是使數組中的每個元素與基準值（Pivot，通常是數組的首個值，A[0]）比較，數組中比基準值小的放在基準值的左邊，形成左部；大的放在右邊，形成右部；接下來將左部和右部分別遞歸地執行上面的過程：選基準值，小的放在左邊，大的放在右邊。。。直到排序結束。

步驟：

1.找基準值，設Pivot = a[0]

2.分區（Partition）：比基準值小的放左邊，大的放右邊，基準值(Pivot)放左部與右部的之間。

3.進行左部（a[0] - a[pivot-1]）的遞歸，以及右部（a[pivot+1] - a[n-1]）的遞歸，重復上述步驟。

排序效果：

⑨ java快速排序的遞歸是怎麼實現的，能不能幫我把代碼不完整。。

遞歸實現要遞歸先寫一個代碼塊再遞歸調用這個代碼塊，你沒寫代碼塊只能用循環來寫，你要是想用遞歸的話看看網路的快速排序，裡面寫的很好還有優化的方法。
class Quick
{
public void sort(intarr[],intlow,inthigh)
{
int l=low;
int h=high;
int povit=arr[low];

while(l<h)
{
while(l<h&&arr[h]>=povit)h--;

if(l<h)
{
int temp=arr[h];
arr[h]=arr[l];
arr[l]=temp;
l++;
}

while(l<h&&arr[l]<=povit)l++;

if(l<h)
{
int temp=arr[h];
arr[h]=arr[l];
arr[l]=temp;
h--;
}
}
print(arr);
System.out.print("l="+(l+1)+"h="+(h+1)+"povit="+povit+"\n");
if(l>low)sort(arr,low,h-1);
if(h<high)sort(arr,l+1,high);
}
}
這段你參考一下吧

http://ke..com/view/19016.htm?from_id=2084344&type=syn&fromtitle=%E5%BF%AB%E9%80%9F%E6%8E%92%E5%BA%8F&fr=aladdin

⑩ 那位大大能詳細的講解一下JAVA中的快速排序

快速排序是對冒泡排序的一種改進。它的基本思想是：通過一躺排序將要排序的數據分割成獨立的兩部分，其中一部分的所有數據都比另外一部分的所有數據都要小，然後再按次方法對這兩部分數據分別進行快速排序，整個排序過程可以遞歸進行，以此達到整個數據變成有序序列。最壞情況的時間復雜度為O(n2)，最好情況時間復雜度為O(nlog2n)。

另外 java沒指針概念 可以認為是句柄
假設要排序的數組是A[1]……A[N]，首先任意選取一個數據（通常選用第一個數據）作為關鍵數據，然後將所有比它的數都放到它前面，所有比它大的數都放到它後面，這個過程稱為一躺快速排序。一趟快速排序的演算法是：

1）、設置兩個變數I、J，排序開始的時候I：=1，J：=N；

2）以第一個數組元素作為關鍵數據，賦值給X，即X：=A[1]；

3）、從J開始向前搜索，即由後開始向前搜索（J：=J-1），找到第一個小於X的值，兩者交換；

4）、從I開始向後搜索，即由前開始向後搜索（I：=I+1），找到第一個大於X的值，兩者交換；

5）、重復第3、4步，直到I=J；

例如：待排序的數組A的值分別是：（初始關鍵數據X：=49）

A[1] A[2] A[3] A[4] A[5] A[6] A[7]：

49 38 65 97 76 13 27

進行第一次交換後： 27 38 65 97 76 13 49

( 按照演算法的第三步從後面開始找)

進行第二次交換後： 27 38 49 97 76 13 65

( 按照演算法的第四步從前面開始找>X的值，65>49,兩者交換，此時I：=3 )

進行第三次交換後： 27 38 13 97 76 49 65

( 按照演算法的第五步將又一次執行演算法的第三步從後開始找)

進行第四次交換後： 27 38 13 49 76 97 65

( 按照演算法的第四步從前面開始找大於X的值，97>49,兩者交換，此時J：=4 )

此時再執行第三步的時候就發現I=J，從而結束一躺快速排序，那麼經過一躺快速排序之後的結果是：27 38 13 49 76 97 65，即所以大於49的數全部在49的後面，所以小於49的數全部在49的前面。

快速排序就是遞歸調用此過程——在以49為中點分割這個數據序列，分別對前面一部分和後面一部分進行類似的快速排序，從而完成全部數據序列的快速排序，最後把此數據序列變成一個有序的序列，根據這種思想對於上述數組A的快速排序的全過程如圖6所示：

初始狀態 {49 38 65 97 76 13 27}

進行一次快速排序之後劃分為 {27 38 13} 49 {76 97 65}

分別對前後兩部分進行快速排序 {13} 27 {38}

結束 結束 {49 65} 76 {97}

49 {65} 結束

結束//下面是一個示例,哪位給說說快速排序法的原理,下面的示例中指針和上下標移動我看不太懂,
public class QuickSort {
/**主方法*/
public static void main(String[] args) {
//聲明數組
int[] nums = {27, 8, 57, 9, 23, 41, 65, 19, 0, 1, 2, 4, 5};
//應用快速排序方法
quickSort(nums, 0, nums.length-1);
//顯示排序後的數組
for(int i = 0; i < nums.length; ++i) {
System.out.print(nums[i] + ",");
}
System.out.println("");
}

/**快速排序方法*/
public static void quickSort(int[] a, int lo0, int hi0) {
int lo = lo0;
int hi = hi0;

if (lo >= hi)
return;

//確定指針方向的邏輯變數
boolean transfer=true;

while (lo != hi) {
if (a[lo] > a[hi]) {
//交換數字
int temp = a[lo];
a[lo] = a[hi];
a[hi] = temp;
//決定下標移動，還是上標移動
transfer = (transfer == true) ? false : true;
}

//將指針向前或者向後移動
if(transfer)
hi--;
else
lo++;

//顯示每一次指針移動的數組數字的變化
/*for(int i = 0; i < a.length; ++i) {
System.out.print(a[i] + ",");
}
System.out.print(" (lo,hi) = " + "(" + lo + "," + hi + ")");
System.out.println("");*/
}

//將數組分開兩半，確定每個數字的正確位置
lo--;
hi++;
quickSort(a, lo0, lo);
quickSort(a, hi, hi0);
}
}