排序演算法之快速排序java實現（java實現各種排序演算法）

本文目錄一覽：

• 1、那位大大能詳細的講解一下JAVA中的快速排序
• 2、Java數組排序 幾種排序方法詳細一點
• 3、怎麼用java實現快速排序
• 4、java中快速排序的演算法舉個例子
• 5、請給出java幾種排序方法
• 6、用JAVA實現快速排序演算法？

那位大大能詳細的講解一下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的值，6549,兩者交換，此時I：=3 )

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

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

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

( 按照演算法的第四步從前面開始找大於X的值，9749,兩者交換，此時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);

}

}

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 com.xinhua.test2;

public class Student {

int sno;

String name;

double chiness;

double math;

double english;

double three_sco;

double all_s;

public Student(int sno, String name, double chiness, double math, double english, double three_sco) {

this.sno = sno;

this.name = name;

this.chiness = chiness;

this.math = math;

this.english = english;

this.three_sco = three_sco;

}

@Override

public String toString() {

return “學號：” + sno + “, 名字：” + name + “, 語文成績：” + chiness + “, 數學成績：” + math + “, 英語成績：”

+ english + “總成績：”+(chiness+math+english+three_sco);

}

public static void main(String[] args) {

Student A=new Student(1, “張三”, 118, 145, 114.5, 198);

Student B=new Student(2, “李四”, 130,110.5,100,210);

Student C=new Student(3, “王五”,142.5,120,87.5,245.5);

System.out.println(“學生列表信息為：”);

System.out.println(A.toString());

System.out.println(B.toString());

System.out.println(C.toString());

//

double a_scoAll=A.chiness+A.math+A.english+A.three_sco;

A.all_s=a_scoAll;

double b_scoAll=B.chiness+B.math+B.english+B.three_sco;

B.all_s=b_scoAll;

double c_sclAll=C.chiness+C.math+C.english+C.three_sco;

C.all_s=c_sclAll;

Student[] s_s={A,B,C};

System.out.println(“按總成績從大到小排序為”);

Student temp;

for(int i=0;is_s.length;i++){

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

if(s_s[j-1].all_s s_s[j].all_s){

temp=s_s[j-1] ;

s_s[j-1] =s_s[j];

s_s[j]=temp;

}

}

}

for(int i=0;is_s.length;i++){

System.out.println(“第”+(i+1)+”名為：”+s_s[i].toString());

}

}

}

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: 對集合的快速排序，可以用於ListObject類型數組，

* 隱含意思就是對所有類型數組都適用

* @return

*/

private void sortList() {

ListInteger list = new ArrayListInteger();

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 插入類排序

主要就是對於一個已經有序的序列中，插入一個新的記錄。它包括：直接插入排序，折半插入排序和希爾排序

2 交換類排序

這類排序的核心就是每次比較都要「交換」，在每一趟排序都會兩兩發生一系列的「交換」排序，但是每一趟排序都會讓一個記錄排序到它的最終位置上。它包括：起泡排序，快速排序

3 選擇類排序

每一趟排序都從一系列數據中選擇一個最大或最小的記錄，將它放置到第一個或最後一個為位置交換，只有在選擇後才交換，比起交換類排序，減少了交換記錄的時間。屬於它的排序：簡單選擇排序，堆排序

4 歸併類排序

將兩個或兩個以上的有序序列合併成一個新的序列

5 基數排序

主要基於多個關鍵字排序的。

下面針對上面所述的演算法，講解一些常用的java代碼寫的演算法

二 插入類排序之直接插入排序

直接插入排序,一般對於已經有序的隊列排序效果好。

基本思想：每趟將一個待排序的關鍵字按照大小插入到已經排序好的位置上。

演算法思路，從後往前先找到要插入的位置，如果小於則就交換，將元素向後移動，將要插入數據插入該位置即可。時間複雜度為O(n2),空間複雜度為O(1)

package sort.algorithm;

public class DirectInsertSort {

public static void main(String[] args) {

// TODO Auto-generated method stub

int data[] = { 2, 6, 10, 3, 9, 80, 1, 16, 27, 20 };

int temp, j;

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

temp = data[i];

j = i – 1;

// 每次比較都是對於已經有序的

while (j = 0 data[j] temp) {

data[j + 1] = data[j];

j–;

}

data[j + 1] = temp;

}

// 輸出排序好的數據

for (int k = 0; k data.length; k++) {

System.out.print(data[k] + ” “);

}

}

}

三 插入類排序之折半插入排序(二分法排序)

條件：在一個已經有序的隊列中，插入一個新的元素

折半插入排序記錄的比較次數與初始序列無關

思想：折半插入就是首先將隊列中取最小位置low和最大位置high，然後算出中間位置mid

將中間位置mid與待插入的數據data進行比較，

如果mid大於data，則就表示插入的數據在mid的左邊，high=mid-1;

如果mid小於data，則就表示插入的數據在mid的右邊,low=mid+1

最後整體進行右移操作。

時間複雜度O(n2),空間複雜度O(1)

package sort.algorithm;

//折半插入排序

public class HalfInsertSort {

public static void main(String[] args) {

int data[] = { 2, 6, 10, 3, 9, 80, 1, 16, 27, 20 };

// 存放臨時要插入的元素數據

int temp;

int low, mid, high;

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

temp = data[i];

// 在待插入排序的序號之前進行折半插入

low = 0;

high = i – 1;

while (low = high) {

mid = (low + high) / 2;

if (temp data[mid])

high = mid – 1;

else

// low=high的時候也就是找到了要插入的位置，

// 此時進入循環中，將low加1，則就是要插入的位置了

low = mid + 1;

}

// 找到了要插入的位置，從該位置一直到插入數據的位置之間數據向後移動

for (int j = i; j = low + 1; j–)

data[j] = data[j – 1];

// low已經代表了要插入的位置了

data[low] = temp;

}

for (int k = 0; k data.length; k++) {

System.out.print(data[k] + ” “);

}

}

}

四 插入類排序之希爾排序

希爾排序，也叫縮小增量排序，目的就是儘可能的減少交換次數，每一個組內最後都是有序的。

將待續按照某一種規則分為幾個子序列，不斷縮小規則，最後用一個直接插入排序合成

空間複雜度為O(1)，時間複雜度為O(nlog2n)

演算法先將要排序的一組數按某個增量d（n/2,n為要排序數的個數）分成若干組，每組中記錄的下標相差d.對每組中全部元素進行直接插入排序，然後再用一個較小的增量（d/2）對它進行分組，在每組中再進行直接插入排序。當增量減到1時，進行直接插入排序後，排序完成。

package sort.algorithm;

public class ShellSort {

public static void main(String[] args) {

int a[] = { 1, 54, 6, 3, 78, 34, 12, 45, 56, 100 };

double d1 = a.length;

int temp = 0;

while (true)

{

//利用這個在將組內倍數減小

//這裡依次為5,3,2,1

d1 = Math.ceil(d1 / 2);

//d為增量每個分組之間索引的增量

int d = (int) d1;

//每個分組內部排序

for (int x = 0; x d; x++)

{

//組內利用直接插入排序

for (int i = x + d; i a.length; i += d) {

int j = i – d;

temp = a[i];

for (; j = 0 temp a[j]; j -= d) {

a[j + d] = a[j];

}

a[j + d] = temp;

}

}

if (d == 1)

break;

}

for (int i = 0; i a.length; i++)

System.out.print(a[i]+” “);

}

}

五 交換類排序之冒泡排序

交換類排序核心就是每次比較都要進行交換

冒泡排序：是一種交換排序

每一趟比較相鄰的元素，較若大小不同則就會發生交換，每一趟排序都能將一個元素放到它最終的位置！每一趟就進行比較。

時間複雜度O(n2)，空間複雜度O(1)

package sort.algorithm;

//冒泡排序：是一種交換排序

public class BubbleSort {

// 按照遞增順序排序

public static void main(String[] args) {

// TODO Auto-generated method stub

int data[] = { 2, 6, 10, 3, 9, 80, 1, 16, 27, 20, 13, 100, 37, 16 };

int temp = 0;

// 排序的比較趟數,每一趟都會將剩餘最大數放在最後面

for (int i = 0; i data.length – 1; i++) {

// 每一趟從開始進行比較，將該元素與其餘的元素進行比較

for (int j = 0; j data.length – 1; j++) {

if (data[j] data[j + 1]) {

temp = data[j];

data[j] = data[j + 1];

data[j + 1] = temp;

}

}

}

for (int i = 0; i data.length; i++)

System.out.print(data[i] + ” “);

}

}

用JAVA實現快速排序演算法？

本人特地給你編的代碼

親測

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

}

}