JAVA語言的常見排序算法

相關推薦

JAVA語言的常見排序算法

　　導語：每種排序算法都有它自己的優點及局限性，適用于不同的要求范圍，在選擇時應根據需要適當選用，甚至可將多種算法結合起來使用，效率才會更高。下面就由小編為大家介紹一下JAVA語言的常見排序算法，歡迎大家閱讀!

　　1 排序算法概述

　　計算機中的排序，就是使一串記錄，按照其中的某個或某些關鍵字的大小，遞增或遞減的排列起來的操作。而排序算法則是一種能將一串數據依照特定的方式進行排序的一種算法。

　　根據排序過程中涉及的存儲器不同，可以將排序方法分為兩大類：一類是內部排序，指的是待排序地記錄存放在計算機隨機存儲器中進行的排序過程。另一類是外部排序，指的是需要對外存儲器進行訪問的排序過程。該課題主要研究幾類常見的內部排序，有冒泡排序、插入排序、選擇排序、歸并排序。

　　2 常見排序算法基本思想和JAVA代碼實現

　　2.1 冒泡排序

　　2.1.1 基本思想

　　冒泡排序是將相鄰的兩個記錄按關鍵值兩兩比較，如果記錄的次序相反時即進行交換，直到序列中不存在反序的記錄為止。如有n個無序數，第一趟將第一個和第二個進行比較，將大的放在第二個位置，再將第二個和第三比較，大的放在第三個位置，依次向后比較，比較n-1次，將最大的放在最后(n的位置);第二趟，再從第一個開始比較，比較n-2次，這次把最大的放到第n-1個位置，然后再來回比較。遵循第i次遍歷就從第一個數開始比較n-i次，將最后的值放在第n-i+1的位置。如圖1、圖2所示。

　　2.1.2 JAVA語言實現冒泡排序核心代碼

　　//冒泡排序：10萬個隨機數用時約25秒

　　public static voidbubblesort (int a[]){

　　inti，j，temp;

　　int n=a。length; //獲得數組長度

　　for(i=1;i<=n;i++){ //外層循環控制比較趟數

　　for( j=0;j　　if(a[j]>a[j+1]){//如果相鄰兩數前者比后者大，那交換

　　temp=a[j];

　　a[j]=a[j+1];

　　a[j+1]=temp;

　　}

　　2.2 插入排序

　　2.2.1 基本思想

　　插入排序是一種簡單的排序方法，它的基本排序思想是依次將待排序的記錄逐一地按其關鍵字值的大小插入到一個已排好序的有序序列中，得到一個新的有序序列，直到所有的記錄插完為止，從而實現排序。在有序情況下只需要經過n-1次比較，在最壞情況下，將需要n(n-1)/2次比較，如圖3所示。

　　2.2.2 JAVA語言實現插入排序核心代碼

　　//插入排序：10萬隨機數據用時約7秒

　　public static void sort(int[] arr) {

　　//插入排序：從小到大，從前往后，先找位置后排序

　　//外層循環確定輪次：從第二個到最后一個，n-1輪

　　int j;

　　for(inti=1; i　　//內存循環先找位置：從后(i-1)前找，最多找到0

　　for(j=i-1; j>=0; j--) {

　　//如果找到了比當前數小的，退出//三種情況都確定了j+1為當前數應該排的位置

　　if(arr[j] 　　break;

　　}

　　//再交換排序

　　int temp = arr[i];

　　//從[j+1，i-1]通通往后退一格

　　for(int k=i-1;k>=j+1;k--) {

　　arr[k+1] = arr[k];

　　}//j+1這個位置讓我排

　　arr[j+1] = temp;

　　}

　　2.3 選擇排序

　　2.3.1 基本思想　　選擇排序是在待排序的一組數據元素中，選出最小的一個數據元素與第一個位置的數據元素交換;然后在剩下的數據元素當中再找最小的與第二個位置的數據元素交換，循環到只剩下最后一個數據元素為止。它的比較次數是一定的：n(n-1)/2。因此無論何種序列，正序和反序數據耗時相差不多，相差的只是數據移動時間，對數據的有序性不敏感。它雖然比較次數多，但它的數據交換量卻很少。如圖4所示。

　　2.3.2 JAVA語言實現選擇排序核心代碼

　　//選擇排序：10萬隨機數據用時約8秒

　　public static void selectsort(int[] arr) {

　　//外層循環確定輪次(n-1)

　　int min;

　　int index;

　　for(inti=0; i　　//內層循環確定比較和交換范圍

　　min = arr[i];

　　index = i;

　　for(int j=i+1;j　　//比較和交換

　　if(min >arr[j]) {

　　min = arr[j];

　　index = j;

　　}

　　if(i != index) {

　　int temp = arr[i];

　　arr[i] = arr[index];

　　arr[index] = temp;

　　}

　　2.4 歸并排序

　　2.4.1 基本思想

　　歸并排序要求待排序列已經部分有序。部分有序的含義是待排序列由若干個有序的子序列組成。歸并排序的基本思想是：將這些有序的子序列進行合并，從而得到有序的序列。合并是一種常見運算，其方法是：比較各子序列的第一個記錄的鍵值，最小的一個就是排序后序列的第一個記錄的鍵值。取出這個記錄，繼續比較各子序列現在的第一個記錄的鍵值，便可找出排序后的第二記錄。如此繼續下去，最終可以得到排序結果。因此，歸并排序的基礎是合并，如圖5所示。

　　2.4.2 JAVA 語言實現歸并排序核心代碼

　　//歸并排序：10萬隨機數據用時約15毫秒

　　public static void merge(int[] arr，int from，int mid，int end，int[] temp) {

　　//分配大數組空間

　　//int[] arr = new int[a。length+b。length];

　　//定義三個下標分別指向a，b，arr

　　inti=from，j=mid+1，k=from;

　　//比較，取值，直到其中一個數組結束

　　while(i<=mid && j<=end) {

　　if(arr[i] 　　temp[k++] = arr[i++];

　　}else {

　　temp[k++] = arr[j++];