java快速排序,Java快速排序時間複雜度

本文目錄一覽：

• 1、Java數組排序 幾種排序方法詳細一點
• 2、請問一下java快速排序源代碼
• 3、Java的幾種常見排序
• 4、java快速排序簡單代碼
• 5、如何理解java數據結構中的快速排序方法

Java數組排序 幾種排序方法詳細一點

JAVA中在運用數組進行排序功能時，一般有四種方法：快速排序法、冒泡法、選擇排序法、插入排序法。

快速排序法主要是運用了Arrays中的一個方法Arrays.sort（）實現。

冒泡法是運用遍曆數組進行比較，通過不斷的比較將最小值或者最大值一個一個的遍歷出來。

選擇排序法是將數組的第一個數據作為最大或者最小的值，然後通過比較循環，輸出有序的數組。

插入排序是選擇一個數組中的數據，通過不斷的插入比較最後進行排序。下面我就將他們的實現方法一一詳解供大家參考。

1利用Arrays帶有的排序方法快速排序

public class Test2{   

        public static void main(String[] args){   

                int[] a={5,4,2,4,9,1};   

                Arrays.sort(a);  //進行排序   

                for(int i: a){   

                        System.out.print(i);   

               }  

        }  

}

2冒泡排序演算法

public static int[] bubbleSort(int[] args){//冒泡排序演算法   

        for(int i=0;iargs.length-1;i++){   

               for(int j=i+1;jargs.length;j++){   

                   if (args[i]args[j]){   

                       int temp=args[i];   

                       args[i]=args[j];   

                       args[j]=temp;   

                       }   

            }  

       }  

       return args;  

}

3選擇排序演算法

public static int[] selectSort(int[] args){//選擇排序演算法   

         for (int i=0;iargs.length-1 ;i++ ){   

                int min=i;   

                for (int j=i+1;jargs.length ;j++ ){   

                      if (args[min]args[j]){   

                           min=j;   

                           }   

                  }   

                      if (min!=i){  

                      int temp=args[i];  

                      args[i]=args[min];  

                      args[min]=temp;          

                  }  

            }  

             return args;  

    }

4插入排序演算法

public static int[] insertSort(int[] args){//插入排序演算法   

                 for(int i=1;iargs.length;i++){   

                         for(int j=i;j0;j–){   

                                 if (args[j]args[j-1]){   

                                         int temp=args[j-1];  

                                         args[j-1]=args[j];  

                                        args[j]=temp;          

                                }else break;   

                        }  

                 }  

                 return args;  

         }

請問一下java快速排序源代碼

快速排序：

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);

}

}

}

}

Java的幾種常見排序

快速排序法、冒泡法、選擇排序法、插入排序法

1.快速排序：

import java.util.Arrays;

public class Test2{

public static void main(String[] args){

int[] a={5,4,2,4,9,1};

Arrays.sort(a); //進行排序

for(int i: a){

System.out.print(i);

}

}

}

2.冒泡排序

public static int[] bubbleSort(int[] args){//冒泡排序演算法

for(int i=0;iargs.length-1;i++){

for(int j=i+1;jargs.length;j++){

if (args[i]args[j]){

int temp=args[i];

args[i]=args[j];

args[j]=temp;

}

}

}

return args;

}

3.選擇排序

public static int[] selectSort(int[] args){//選擇排序演算法

for (int i=0;iargs.length-1 ;i++ ){

int min=i;

for (int j=i+1;jargs.length ;j++ ){

if (args[min]args[j]){

min=j;

}

}

if (min!=i){

int temp=args[i];

args[i]=args[min];

args[min]=temp;

}

}

return args;

}

4.插入排序

public static int[] insertSort(int[] args){//插入排序演算法

for(int i=1;iargs.length;i++){

for(int j=i;j0;j–){

if (args[j]args[j-1]){

int temp=args[j-1];

args[j-1]=args[j];

args[j]=temp;

}else break;

}

}

return args;

}

java快速排序簡單代碼

.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} 排序演算法是《數據結構與演算法》中最基本的演算法之一。排序演算法可以分為內部排序和外部排序，內部排序是數據記錄在內存中進行排序，而外部排序是因排序的數據很大，一次不能容納全部的排序記錄，在排序過程中需要訪問外存。常見的內部排序演算法有：插入排序、希爾排序、選擇排序、冒泡排序、歸併排序、快速排序、堆排序、基數排序等。以下是快速排序演算法：

快速排序是由東尼·霍爾所發展的一種排序演算法。在平均狀況下，排序 n 個項目要 Ο(nlogn) 次比較。在最壞狀況下則需要 Ο(n2) 次比較，但這種狀況並不常見。事實上，快速排序通常明顯比其他 Ο(nlogn) 演算法更快，因為它的內部循環（inner loop）可以在大部分的架構上很有效率地被實現出來。

快速排序使用分治法（Divide and conquer）策略來把一個串列（list）分為兩個子串列（sub-lists）。

快速排序又是一種分而治之思想在排序演算法上的典型應用。本質上來看，快速排序應該算是在冒泡排序基礎上的遞歸分治法。

快速排序的名字起的是簡單粗暴，因為一聽到這個名字你就知道它存在的意義，就是快，而且效率高！它是處理大數據最快的排序演算法之一了。雖然 Worst Case 的時間複雜度達到了 O(n?)，但是人家就是優秀，在大多數情況下都比平均時間複雜度為 O(n logn) 的排序演算法表現要更好，可是這是為什麼呢，我也不知道。好在我的強迫症又犯了，查了 N 多資料終於在《演算法藝術與信息學競賽》上找到了滿意的答案：

快速排序的最壞運行情況是 O(n?)，比如說順序數列的快排。但它的平攤期望時間是 O(nlogn)，且 O(nlogn) 記號中隱含的常數因子很小，比複雜度穩定等於 O(nlogn) 的歸併排序要小很多。所以，對絕大多數順序性較弱的隨機數列而言，快速排序總是優於歸併排序。

1. 演算法步驟

從數列中挑出一個元素，稱為 “基準”（pivot）;

重新排序數列，所有元素比基準值小的擺放在基準前面，所有元素比基準值大的擺在基準的後面（相同的數可以到任一邊）。在這個分區退出之後，該基準就處於數列的中間位置。這個稱為分區（partition）操作；

遞歸地（recursive）把小於基準值元素的子數列和大於基準值元素的子數列排序；

2. 動圖演示

代碼實現 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

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

原理：

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

步驟：

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

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

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

排序效果：