JAVA排序匯總

2019-11-17 03:59:59

字體：大中小

供稿：網(wǎng)友

import java.util.Random;



/**

  * 排序測試類

  *

  * 排序算法的分類如下：

  * 1. 插入排序（直接插入排序、折半插入排序、希爾排序）；

  * 2. 交換排序（冒泡泡排序、快速排序）；

  * 3. 選擇排序（直接選擇排序、堆排序）；

  * 4. 歸并排序；

  * 5. 基數(shù)排序。

  *

  * 關(guān)于排序方法的選擇：

  * (1) 若 n 較小 ( 如 n≤50) ，可采用直接插入或直接選擇排序。

  * 　當記錄規(guī)模較小時，直接插入排序較好；否則因為直接選擇移動的記錄數(shù)少于直接插人，應(yīng)選直接選擇排序為宜。

  * (2) 若文件初始狀態(tài)基本有序 ( 指正序 ) ，則應(yīng)選用直接插人、冒泡或隨機的快速排序為宜；

  * (3) 若 n 較大，則應(yīng)采用時間復雜度為 O(nlgn) 的排序方法：快速排序、堆排序或歸并排序。

  *

  */

public class SortTest {



       /**

         * 初始化測試數(shù)組的方法

         * @return 一個初始化好的數(shù)組

         */

       public int [] createArray() {

              Random random = new Random();

              int [] array = new int [10];

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

                     array[i] = random.nextInt(100) - random.nextInt(100); // 生成兩個隨機數(shù)相減，保證生成的數(shù)中有負數(shù)

              }

              System. out .PRintln( "========== 原始序列 ==========" );

              printArray(array);

              return array;

       }



       /**

         * 打印數(shù)組中的元素到控制臺

         * @param source

         */

       public void printArray( int [] data) {

              for ( int i : data) {

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

              }

              System. out .println();

       }



       /**

         * 交換數(shù)組中指定的兩元素的位置

         * @param data

         * @param x

         * @param y

         */

       private void swap( int [] data, int x, int y) {

              int temp = data[x];

              data[x] = data[y];

              data[y] = temp;

       }



       /**

         * 冒泡排序 ---- 交換排序的一種

         * 方法：相鄰兩元素進行比較，如有需要則進行交換，每完成一次循環(huán)就將最大元素排在最后（如從小到大排序），下一次循環(huán)是將其他的數(shù)進行類似操作。

         * 性能：比較次數(shù) O(n^2),n^2/2 ；交換次數(shù) O(n^2),n^2/4

         *

         * @param data 要排序的數(shù)組

         * @param sortType 排序類型

         * @return

         */

       public void bubbleSort( int [] data, String sortType) {

              if (sortType.equals( "asc" )) { // 正排序，從小排到大

                     // 比較的輪數(shù)

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

                            // 將相鄰兩個數(shù)進行比較，較大的數(shù)往后冒泡

                            for ( int j = 0; j < data. length - i; j++) {

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

                                          // 交換相鄰兩個數(shù)

                                          swap(data, j, j + 1);

                                   }

                            }

                     }

              } else if (sortType.equals( "desc" )) { // 倒排序，從大排到小

                     // 比較的輪數(shù)

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

                            // 將相鄰兩個數(shù)進行比較，較大的數(shù)往后冒泡

                            for ( int j = 0; j < data. length - i; j++) {

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

                                          // 交換相鄰兩個數(shù)

                                          swap(data, j, j + 1);

                                   }

                            }

                     }

              } else {

                     System. out .println( " 您輸入的排序類型錯誤！ " );

              }

              printArray(data); // 輸出冒泡排序后的數(shù)組值

       }



       /**

         * 直接選擇排序法 ---- 選擇排序的一種

         * 方法：每一趟從待排序的數(shù)據(jù)元素中選出最小（或最大）的一個元素，順序放在已排好序的數(shù)列的最后，直到全部待排序的數(shù)據(jù)元素排完。

         * 性能：比較次數(shù) O(n^2),n^2/2

         *        交換次數(shù) O(n),n

         *        交換次數(shù)比冒泡排序少多了，由于交換所需 CPU 時間比比較所需的 CUP 時間多，所以選擇排序比冒泡排序快。

         *        但是 N 比較大時，比較所需的 CPU 時間占主要地位，所以這時的性能和冒泡排序差不太多，但毫無疑問肯定要快些。

         *

         * @param data 要排序的數(shù)組

         * @param sortType 排序類型

         * @return

         */

       public void selectSort( int [] data , String sortType) {



              if (sortType.equals( "asc" )) { // 正排序，從小排到大

                     int index;

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

                            index = 0;

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

                                   if (data [j] > data [index]) {

                                          index = j;



                                   }

                            }

                            // 交換在位置 data.length-i 和 index( 最大值 ) 兩個數(shù)

                            swap(data , data . length - i, index);

                     }

              } else if (sortType.equals( "desc" )) { // 倒排序，從大排到小

                     int index;

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

                            index = 0;

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

                                   if (data [j] < data [index]) {

                                          index = j;



                                   }

                            }

                            // 交換在位置 data.length-i 和 index( 最大值 ) 兩個數(shù)

                            swap(data , data . length - i, index);

                     }

              } else {

                     System. out .println( " 您輸入的排序類型錯誤！ " );

              }

              printArray(data ); // 輸出直接選擇排序后的數(shù)組值

       }



       /**

         * 插入排序

         * 方法：將一個記錄插入到已排好序的有序表（有可能是空表）中 , 從而得到一個新的記錄數(shù)增 1 的有序表。

         * 性能：比較次數(shù) O(n^2),n^2/4

         *        復制次數(shù) O(n),n^2/4

         *        比較次數(shù)是前兩者的一般，而復制所需的 CPU 時間較交換少，所以性能上比冒泡排序提高一倍多，而比選擇排序也要快。

         *

         * @param data 要排序的數(shù)組

         * @param sortType 排序類型

         */

       public void insertSort( int [] data, String sortType) {

              if (sortType.equals( "asc" )) { // 正排序，從小排到大

                     // 比較的輪數(shù)

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

                            // 保證前 i+1 個數(shù)排好序

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

                                   if (data[j] > data[i]) {

                                          // 交換在位置 j 和 i 兩個數(shù)

                                          swap(data, i, j);

                                   }

                            }

                     }

              } else if (sortType.equals( "desc" )) { // 倒排序，從大排到小

                     // 比較的輪數(shù)

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

                            // 保證前 i+1 個數(shù)排好序

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

                                   if (data[j] < data[i]) {

                                          // 交換在位置 j 和 i 兩個數(shù)

                                          swap(data, i, j);

                                   }

                            }

                     }

              } else {

                     System. out .println( " 您輸入的排序類型錯誤！ " );

              }

              printArray(data); // 輸出插入排序后的數(shù)組值

       }



       /**

         * 反轉(zhuǎn)數(shù)組的方法

         * @param data 源數(shù)組

         */

       public void reverse( int [] data) {



              int length = data. length ;

              int temp = 0; // 臨時變量



              for ( int i = 0; i < length / 2; i++) {

                     temp = data[i];

                     data[i] = data[length - 1 - i];

                     data[length - 1 - i] = temp;

              }

              printArray(data); // 輸出到轉(zhuǎn)后數(shù)組的值

       }



       /**

         * 快速排序

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

         * 步驟為：

         * 1. 從數(shù)列中挑出一個元素，稱為 " 基準 " （ pivot ），

         * 2. 重新排序數(shù)列，所有元素比基準值小的擺放在基準前面，所有元素比基準值大的擺在基準的后面（相同的數(shù)可以到任一邊）。在這個分割之后，該基準是它的最后位置。這個稱為分割（ partition ）操作。

         * 3. 遞歸地（ recursive ）把小于基準值元素的子數(shù)列和大于基準值元素的子數(shù)列排序。

         * 遞回的最底部情形，是數(shù)列的大小是零或一，也就是永遠都已經(jīng)被排序好了。雖然一直遞回下去，但是這個算法總會結(jié)束，因為在每次的迭代（ iteration ）中，它至少會把一個元素擺到它最后的位置去。

         * @param data 待排序的數(shù)組

         * @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( " 您輸入的排序類型錯誤！ " );

              }

       }



       /**

         * 快速排序的具體實現(xiàn)，排正序

         * @param data

         * @param low

         * @param high

         */

       private void qsort_asc( int data[], int low, int high) {

              int i, j, x;

              if (low < high) { // 這個條件用來結(jié)束遞歸

                     i = low;

                     j = high;

                     x = data[i];

                     while (i < j) {

                            while (i < j && data[j] > x) {

                                   j--; // 從右向左找第一個小于 x 的數(shù)

                            }

                            if (i < j) {

                                   data[i] = data[j];

                                   i++;

                            }

                            while (i < j && data[i] < x) {

                                   i++; // 從左向右找第一個大于 x 的數(shù)

                            }

                            if (i < j) {

                                   data[j] = data[i];

                                   j--;

                            }

                     }

                     data[i] = x;

                     qsort_asc(data, low, i - 1);

                     qsort_asc(data, i + 1, high);

              }

       }



       /**

         * 快速排序的具體實現(xiàn)，排倒序

         * @param data

         * @param low

         * @param high

         */

       private void qsort_desc( int data[], int low, int high) {

              int i, j, x;

              if (low < high) { // 這個條件用來結(jié)束遞歸

                     i = low;

                     j = high;

                     x = data[i];

                     while (i < j) {

                            while (i < j && data[j] < x) {

                                   j--; // 從右向左找第一個小于 x 的數(shù)

                            }

                            if (i < j) {

                                   data[i] = data[j];

                                   i++;

                            }

                            while (i < j && data[i] > x) {

                                   i++; // 從左向右找第一個大于 x 的數(shù)

                            }

                            if (i < j) {

                                   data[j] = data[i];

                                   j--;

                            }

                     }

                     data[i] = x;

                     qsort_desc(data, low, i - 1);

                     qsort_desc(data, i + 1, high);

              }

       }



       /**

         * 二分查找特定整數(shù)在整型數(shù)組中的位置 ( 遞歸 )

         * 查找線性表必須是有序列表

         * @paramdataset

         * @paramdata

         * @parambeginIndex

         * @paramendIndex

         * @returnindex

         */

       public int binarySearch( int [] dataset, int data, int beginIndex,

                     int endIndex) {

              int midIndex = (beginIndex + endIndex) >>> 1; // 相當于 mid = (low + high) / 2 ，但是效率會高些

              if (data < dataset[beginIndex] || data > dataset[endIndex]

                            || beginIndex > endIndex)

                     return -1;

              if (data < dataset[midIndex]) {

                     return binarySearch(dataset, data, beginIndex, midIndex - 1);

              } else if (data > dataset[midIndex]) {

                     return binarySearch(dataset, data, midIndex + 1, endIndex);

              } else {

                     return midIndex;

              }

       }



       /**

         * 二分查找特定整數(shù)在整型數(shù)組中的位置 ( 非遞歸 )

         * 查找線性表必須是有序列表

         * @paramdataset

         * @paramdata

         * @returnindex

         */

       public int binarySearch( int [] dataset, int data) {

              int beginIndex = 0;

              int endIndex = dataset. length - 1;

              int midIndex = -1;

              if (data < dataset[beginIndex] || data > dataset[endIndex]

                            || beginIndex > endIndex)

                     return -1;

              while (beginIndex <= endIndex) {

                     midIndex = (beginIndex + endIndex) >>> 1; // 相當于 midIndex = (beginIndex + endIndex) / 2 ，但是效率會高些

                     if (data < dataset[midIndex]) {

                            endIndex = midIndex - 1;

                     } else if (data > dataset[midIndex]) {

                            beginIndex = midIndex + 1;

                     } else {

                            return midIndex;

                     }

              }

              return -1;

       }



       public static void main(String[] args) {

              SortTest sortTest = new SortTest();



              int [] array = sortTest.createArray();



              System. out .println( "========== 冒泡排序后 ( 正序 )==========" );

              sortTest.bubbleSort(array, "asc" );

              System. out .println( "========== 冒泡排序后 ( 倒序 )==========" );

              sortTest.bubbleSort(array, "desc" );



              array = sortTest.createArray();



              System. out .println( "========== 倒轉(zhuǎn)數(shù)組后 ==========" );

              sortTest.reverse(array);



              array = sortTest.createArray();



              System. out .println( "========== 選擇排序后 ( 正序 )==========" );

              sortTest.selectSort(array, "asc" );

              System. out .println( "========== 選擇排序后 ( 倒序 )==========" );

              sortTest.selectSort(array, "desc" );



              array = sortTest.createArray();



              System. out .println( "========== 插入排序后 ( 正序 )==========" );

              sortTest.insertSort(array, "asc" );

              System. out .println( "========== 插入排序后 ( 倒序 )==========" );

              sortTest.insertSort(array, "desc" );



              array = sortTest.createArray();

              System. out .println( "========== 快速排序后 ( 正序 )==========" );

              sortTest.quickSort(array, "asc" );

              sortTest.printArray(array);

              System. out .println( "========== 快速排序后 ( 倒序 )==========" );

              sortTest.quickSort(array, "desc" );

              sortTest.printArray(array);



              System. out .println( "========== 數(shù)組二分查找 ==========" );

              System. out .println( " 您要找的數(shù)在第 " + sortTest.binarySearch(array, 74)

                            + " 個位子。（下標從 0 計算） " );

       }

}

上一篇：Java中的mac計算

下一篇：java判斷出棧順序是否正確