排序算法說明

排序說明

對一序列對象根據某個關鍵字進行排序。

術語說明

穩定：如果a原本在b前面，而a=b，排序之后a仍然在b的前面；

不穩定：如果a原本在b的前面，而a=b，排序之后a可能會出現在b的后面；

內排序：所有排序操作都在內存中完成；

外排序：由于數據太大，因此把數據放在磁盤中，而排序通過磁盤和內存的數據傳輸才能進行；

時間復雜度： 一個算法執行所耗費的時間。

空間復雜度：運行完一個程序所需內存的大小。

算法總結

名詞解釋：

n: 數據規模

k: “桶”的個數

In-place: 占用常數內存，不占用額外內存

Out-place: 占用額外內存

分類

內部排序(使用內存)

插入排序

直接插入排序

希爾排序

選擇排序

簡單選擇排序

堆排序

交換排序

冒泡排序

快速排序

歸并排序

基數排序

外部排序(內存、外存結合使用)

比較排序與非比較排序

常見的快速排序、歸并排序、堆排序、冒泡排序等屬于比較排序。在排序的最終結果里，元素之間的次序依賴于它們之間的比較。每個數都必須和其他數進行比較，才能確定自己的位置。在冒泡排序之類的排序中，問題規模為n，又因為需要比較n次，所以平均時間復雜度為O(n2)。在歸并排序、快速排序之類的排序中，問題規模通過分治法消減為logN次，所以時間復雜度平均O(nlogn)。

比較排序的優勢是，適用于各種規模的數據，也不在乎數據的分布，都能進行排序。可以說，比較排序適用于一切需要排序的情況。

計數排序、基數排序、桶排序則屬于非比較排序。非比較排序是通過確定每個元素之前，應該有多少個元素來排序。針對數組arr，計算arr[i]之前有多少個元素，則唯一確定了arr[i]在排序后數組中的位置。非比較排序只要確定每個元素之前的已有的元素個數即可，所有一次遍歷即可解決。算法時間復雜度O(n)。非比較排序時間復雜度底，但由于非比較排序需要占用空間來確定唯一位置。所以對數據規模和數據分布有一定的要求。

冒泡排序

介紹

冒泡排序是一種簡單的排序算法。它重復地走訪過要排序的數列，一次比較兩個元素，如果它們的順序錯誤就把它們交換過來。走訪數列的工作是重復地進行直到沒有再需要交換，也就是說該數列已經排序完成。這個算法的名字由來是因為越小的元素會經由交換慢慢“浮”到數列的頂端。

描述

比較相鄰的元素。如果第一個比第二個大，就交換它們兩個；

對每一對相鄰元素作同樣的工作，從開始第一對到結尾的最后一對，這樣在最后的元素應該會是最大的數；

針對所有的元素重復以上的步驟，除了最后一個；

重復步驟1~3，直到排序完成。

演示

?

示例代碼

package study1;

import java.util.Scanner;

public class a {

public static void main(String[] args) {

int[] array1 = new int[10];

System.out.println("請輸入需要排列的十個整數：");

Scanner getNumber = new Scanner(System.in);

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

array1[i] = getNumber.nextInt();

}

//冒泡排序

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

for(int j=0; j

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

int temp = array1[j];

array1[j] = array1[j+1];

array1[j+1] = temp;

}

}

}

System.out.println("排序完成！");

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

System.out.println(array1[i]);

}

}

}

理解

對相鄰的元素進行兩兩比較，順序相反則交換，這樣，每趟會將最小(或最大)的元素浮到數組最后面，最終達到整體有序。

N個數字要排序完成，總共進行N-1次排序，每i次的排序比較的次數為(N-i)次，所以可以用雙重循環語句，外層控制循環多少次，內層控制每一次的比較次數

每次循環都會將本次參與循環的數字中的最大的一個放置在最后，因而在之后的每次排序中所參與的數字會一次減少。

選擇排序

介紹

表現最穩定的排序算法之一，因為無論什么數據進去都是O(n2)的時間復雜度，所以用到它的時候，數據規模越小越好。唯一的好處可能就是不占用額外的內存空間了吧。理論上講，選擇排序可能也是平時排序一般人想到的最多的排序方法了吧。

選擇排序(Selection-sort)是一種簡單直觀的排序算法。它的工作原理：首先在未排序序列中找到最小(大)元素，存放到排序序列的起始位置，然后，再從剩余未排序元素中繼續尋找最小(大)元素，然后放到已排序序列的末尾。以此類推，直到所有元素均排序完畢。

描述

n個記錄的直接選擇排序可經過n-1趟直接選擇排序得到有序結果。具體算法描述如下：

初始狀態：無序區為R[1…n]，有序區為空；

第i趟排序(i=1,2,3…n-1)開始時，當前有序區和無序區分別為R[1…i-1]和R(i…n)。該趟排序從當前無序區中-選出關鍵字最小的記錄 R[k]，將它與無序區的第1個記錄R交換，使R[1…i]和R[i+1…n)分別變為記錄個數增加1個的新有序區和記錄個數減少1個的新無序區；

n-1趟結束，數組有序化了。

演示

?

示例代碼

package study1;

public class a {

public static void main(String[] args) {

int[] array = {11, 21, 4, 65, 32, 7};

for(int i=0; i

int minIndex = i;

for(int j=i; j

if(array[j] < array[minIndex]){

minIndex = j;

}

}

int temp = array[minIndex];

array[minIndex] = array[i];

array[i] = temp;

}

for(int k=0; k

System.out.println(array[k]);

}

}

}

理解

每次遍歷數組，將所遍歷的最小值放置在最前，每次完成一次遍歷后，調整遍歷的起始位置(同時也是將剩余數值篩選出所放置的位置)，依次類推。

插入排序

介紹

插入排序(Insertion-Sort)的算法描述是一種簡單直觀的排序算法。它的工作原理是通過構建有序序列，對于未排序數據，在已排序序列中從后向前掃描，找到相應位置并插入。插入排序在實現上，通常采用in-place排序(即只需用到O(1)的額外空間的排序)，因而在從后向前掃描過程中，需要反復把已排序元素逐步向后挪位，為最新元素提供插入空間。

描述

從第一個元素開始，該元素可以認為已經被排序；

取出下一個元素，在已經排序的元素序列中從后向前掃描；

如果該元素(已排序)大于新元素，將該元素移到下一位置；

重復步驟3，直到找到已排序的元素小于或者等于新元素的位置；

將新元素插入到該位置后；

重復步驟2~5。

演示

?

示例代碼

package study1;

public class a {

public static void main(String[] args) {

int[] array = {11, 21, 4, 65, 32, 7};

int current;

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

current = array[i + 1]; // 當前排序到的元素

int preIndex = i; // 已經排序完成的最后一個元素的下標

// 將當前排序的元素與每個已完成排序的元素比較

while (preIndex >= 0 && current < array[preIndex]) {

array[preIndex + 1] = array[preIndex];

preIndex--;

}

array[preIndex + 1] = current;

}

for(int j=0; j

System.out.println(array[j]);

}

}

}

理解

將第一個元素視為已經排序完成的元素，從第二個開始與排序好的元素比較，若待排序元素小于當前比較的排序好的元素，那么將該比較大的排序好的元素向后移動，再次將待排序的元素與前一個已經完成排序的元素比較，重復此過程，直到待排序元素匹配到某個已完成排序的元素時添加到其后面。

總結

以上是生活随笔為你收集整理的java冒泡遍历对象_Java经典排序算法（冒泡、选择、插入）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。