快速排序：
創(chuàng)新互聯(lián)成立于2013年，是專業(yè)互聯(lián)網(wǎng)技術服務公司，擁有項目網(wǎng)站制作、做網(wǎng)站網(wǎng)站策劃，項目實施與項目整合能力。我們以讓每一個夢想脫穎而出為使命，1280元柳林做網(wǎng)站,已為上家服務,為柳林各地企業(yè)和個人服務,聯(lián)系電話:18982081108
package org.rut.util.algorithm.support;
import org.rut.util.algorithm.SortUtil;
/**
* @author treeroot
* @since 2006-2-2
* @version 1.0
*/
public class QuickSort implements SortUtil.Sort{
/* (non-Javadoc)
* @see org.rut.util.algorithm.SortUtil.Sort#sort(int[])
*/
public void sort(int[] data) {
quickSort(data,0,data.length-1);
}
private void quickSort(int[] data,int i,int j){
int pivotIndex=(i+j)/2;
//swap
SortUtil.swap(data,pivotIndex,j);
int k=partition(data,i-1,j,data[j]);
SortUtil.swap(data,k,j);
if((k-i)1) quickSort(data,i,k-1);
if((j-k)1) quickSort(data,k+1,j);
}
/**
* @param data
* @param i
* @param j
* @return
*/
private int partition(int[] data, int l, int r,int pivot) {
do{
while(data[++l]pivot);
while((r!=0)data[--r]pivot);
SortUtil.swap(data,l,r);
}
while(lr);
SortUtil.swap(data,l,r);
return l;
}
}
改進后的快速排序：
package org.rut.util.algorithm.support;
import org.rut.util.algorithm.SortUtil;
/**
* @author treeroot
* @since 2006-2-2
* @version 1.0
*/
public class ImprovedQuickSort implements SortUtil.Sort {
private static int MAX_STACK_SIZE=4096;
private static int THRESHOLD=10;
/* (non-Javadoc)
* @see org.rut.util.algorithm.SortUtil.Sort#sort(int[])
*/
public void sort(int[] data) {
int[] stack=new int[MAX_STACK_SIZE];
int top=-1;
int pivot;
int pivotIndex,l,r;
stack[++top]=0;
stack[++top]=data.length-1;
while(top0){
int j=stack[top--];
int i=stack[top--];
pivotIndex=(i+j)/2;
pivot=data[pivotIndex];
SortUtil.swap(data,pivotIndex,j);
//partition
l=i-1;
r=j;
do{
while(data[++l]pivot);
while((r!=0)(data[--r]pivot));
SortUtil.swap(data,l,r);
}
while(lr);
SortUtil.swap(data,l,r);
SortUtil.swap(data,l,j);
if((l-i)THRESHOLD){
stack[++top]=i;
stack[++top]=l-1;
}
if((j-l)THRESHOLD){
stack[++top]=l+1;
stack[++top]=j;
}
}
//new InsertSort().sort(data);
insertSort(data);
}
/**
* @param data
*/
private void insertSort(int[] data) {
int temp;
for(int i=1;idata.length;i++){
for(int j=i;(j0)(data[j]data[j-1]);j--){
SortUtil.swap(data,j,j-1);
}
}
}
}
.example-btn{color:#fff;background-color:#5cb85c;border-color:#4cae4c}.example-btn:hover{color:#fff;background-color:#47a447;border-color:#398439}.example-btn:active{background-image:none}div.example{width:98%;color:#000;background-color:#f6f4f0;background-color:#d0e69c;background-color:#dcecb5;background-color:#e5eecc;margin:0 0 5px 0;padding:5px;border:1px solid #d4d4d4;background-image:-webkit-linear-gradient(#fff,#e5eecc 100px);background-image:linear-gradient(#fff,#e5eecc 100px)}div.example_code{line-height:1.4em;width:98%;background-color:#fff;padding:5px;border:1px solid #d4d4d4;font-size:110%;font-family:Menlo,Monaco,Consolas,"Andale Mono","lucida console","Courier New",monospace;word-break:break-all;word-wrap:break-word}div.example_result{background-color:#fff;padding:4px;border:1px solid #d4d4d4;width:98%}div.code{width:98%;border:1px solid #d4d4d4;background-color:#f6f4f0;color:#444;padding:5px;margin:0}div.code div{font-size:110%}div.code div,div.code p,div.example_code p{font-family:"courier new"}pre{margin:15px auto;font:12px/20px Menlo,Monaco,Consolas,"Andale Mono","lucida console","Courier New",monospace;white-space:pre-wrap;word-break:break-all;word-wrap:break-word;border:1px solid #ddd;border-left-width:4px;padding:10px 15px} 排序算法是《數(shù)據(jù)結(jié)構(gòu)與算法》中最基本的算法之一。排序算法可以分為內(nèi)部排序和外部排序，內(nèi)部排序是數(shù)據(jù)記錄在內(nèi)存中進行排序，而外部排序是因排序的數(shù)據(jù)很大，一次不能容納全部的排序記錄，在排序過程中需要訪問外存。常見的內(nèi)部排序算法有：插入排序、希爾排序、選擇排序、冒泡排序、歸并排序、快速排序、堆排序、基數(shù)排序等。以下是快速排序算法：
快速排序是由東尼·霍爾所發(fā)展的一種排序算法。在平均狀況下，排序 n 個項目要 Ο(nlogn) 次比較。在最壞狀況下則需要 Ο(n2) 次比較，但這種狀況并不常見。事實上，快速排序通常明顯比其他 Ο(nlogn) 算法更快，因為它的內(nèi)部循環(huán)（inner loop）可以在大部分的架構(gòu)上很有效率地被實現(xiàn)出來。
快速排序使用分治法（Divide and conquer）策略來把一個串行（list）分為兩個子串行（sub-lists）。
快速排序又是一種分而治之思想在排序算法上的典型應用。本質(zhì)上來看，快速排序應該算是在冒泡排序基礎上的遞歸分治法。
快速排序的名字起的是簡單粗暴，因為一聽到這個名字你就知道它存在的意義，就是快，而且效率高！它是處理大數(shù)據(jù)最快的排序算法之一了。雖然 Worst Case 的時間復雜度達到了 O(n?)，但是人家就是優(yōu)秀，在大多數(shù)情況下都比平均時間復雜度為 O(n logn) 的排序算法表現(xiàn)要更好，可是這是為什么呢，我也不知道。好在我的強迫癥又犯了，查了 N 多資料終于在《算法藝術與信息學競賽》上找到了滿意的答案：
快速排序的最壞運行情況是 O(n?)，比如說順序數(shù)列的快排。但它的平攤期望時間是 O(nlogn)，且 O(nlogn) 記號中隱含的常數(shù)因子很小，比復雜度穩(wěn)定等于 O(nlogn) 的歸并排序要小很多。所以，對絕大多數(shù)順序性較弱的隨機數(shù)列而言，快速排序總是優(yōu)于歸并排序。
1. 算法步驟
從數(shù)列中挑出一個元素，稱為 "基準"（pivot）;
重新排序數(shù)列，所有元素比基準值小的擺放在基準前面，所有元素比基準值大的擺在基準的后面（相同的數(shù)可以到任一邊）。在這個分區(qū)退出之后，該基準就處于數(shù)列的中間位置。這個稱為分區(qū)（partition）操作；
遞歸地（recursive）把小于基準值元素的子數(shù)列和大于基準值元素的子數(shù)列排序；
2. 動圖演示
代碼實現(xiàn) JavaScript 實例 function quickSort ( arr , left , right ) {
var len = arr. length ,
? ? partitionIndex ,
? ? left = typeof left != 'number' ? 0 : left ,
? ? right = typeof right != 'number' ? len - 1 : right ;
if ( left
① 代碼：
public?class?quicksortdemo?{
private?int?array[];
private?int?length;
public?void?sort(int[]?inputArr)?{
if?(inputArr?==?null?||?inputArr.length?==?0)?{
return;
}
this.array?=?inputArr;
length?=?inputArr.length;
quickSort(0,?length?-?1);
}
private?void?quickSort(int?lowerIndex,?int?higherIndex)?{
int?i?=?lowerIndex;
int?j?=?higherIndex;
//?calculate?pivot?number
int?pivot?=?array[lowerIndex+(higherIndex-lowerIndex)/2];
//?Divide?into?two?arrays
while?(i?=?j)?{
while?(array[i]??pivot)?{
i++;
}
while?(array[j]??pivot)?{
j--;
}
if?(i?=?j)?{
swap(i,?j);????????????????
i++;
j--;
}
}
//?call?quickSort()?method?recursively
if?(lowerIndex??j)
quickSort(lowerIndex,?j);
if?(i??higherIndex)
quickSort(i,?higherIndex);
}
private?void?swap(int?i,?int?j)?{
int?temp?=?array[i];
array[i]?=?array[j];
array[j]?=?temp;
}
public?static?void?main(String?a[]){
quicksortdemo?sorter?=?new?quicksortdemo();
int[]?input?=?{24,2,45,20,56,75,2,56,99,53,12};
sorter.sort(input);
for(int?i:input){
System.out.print(i);
System.out.print("?");
}
}
}
② 運行：
c:\java?quicksortdemo
2?2?12?20?24?45?53?56?56?75?99
本人特地給你編的代碼
親測
public class QuickSort {
public static int Partition(int a[],int p,int r){
int x=a[r-1];
int i=p-1;
int temp;
for(int j=p;j=r-1;j++){
if(a[j-1]=x){
// swap(a[j-1],a[i-1]);
i++;
temp=a[j-1];
a[j-1]=a[i-1];
a[i-1]=temp;
}
}
//swap(a[r-1,a[i+1-1]);
temp=a[r-1];
a[r-1]=a[i+1-1];
a[i+1-1]=temp;
return i+1;
}
public static void QuickSort(int a[],int p,int r){
if(pr){
int q=Partition(a,p,r);
QuickSort(a,p,q-1);
QuickSort(a,q+1,r);
}
}
public static void main(String[] stra){
int a[]={23,53,77,36,84,76,93,13,45,23};
QuickSort(a,1,10);
for (int i=1;i=10;i++)
System.out.println(a[i-1]);
}
}
Java中的快速排序一個簡單的例子
public class QuickSort {
public static void sort(Comparable[] data, int low, int high) {
// 樞紐元,一般以第一個元素為基準進行劃分
Comparable pivotKey = data[low];
// 進行掃描的指針i,j;i從左邊開始,j從右邊開始
int i = low;
int j = high;
if (low high) {
// 從數(shù)組兩端交替地向中間掃描
while (i j) {
while (i j data[j].compareTo(pivotKey) 0) {
j--; }
// end while
if (i j) {
// 比樞紐元素小的移動到左邊
data[i] = data[j];
i++;
}
// end if
while (i j data[i].compareTo(pivotKey) 0) {
i++;
}
// end while
if (i j) {
// 比樞紐元素大的移動到右邊
data[j] = data[i];
j--;
}
// end if
}
// end while
// 樞紐元素移動到正確位置
data[i] = pivotKey;
// 前半個子表遞歸排序
sort(data, low, i - 1);
// 后半個子表遞歸排序
sort(data, i + 1, high);
}
// end if
}
// end sort
public static void main(String[] args) {
// 在JDK1.5版本以上,基本數(shù)據(jù)類型可以自動裝箱
// int,double等基本類型的包裝類已實現(xiàn)了Comparable接口
Comparable[] c = { 4, 9, 23, 1, 45, 27, 5, 2 };
sort(c, 0, c.length - 1);
for (Comparable data : c) {
System.out.println(data);
}
}
}
真的是很服你，你把這個新建一個類放里面
在主方法里面這樣寫：
自己建個數(shù)組Comparable[] data,
定義參數(shù)int low, int high
QuickSort qs = new QuickSort（）；
qs.sort（[] data, low, high）；
重慶分公司
重慶分公司
