|
說起排序算法，可能大家會(huì)脫口而出：冒泡排序，選擇排序。沒錯(cuò)，這是我們最熟悉的兩種排序算法，其實(shí)，排序算法遠(yuǎn)不止這些。而且，你之前寫的冒泡、選擇排序真的是最優(yōu)的嗎？ 一、排序算法的分類總的來說分為兩大類，內(nèi)部排序 和外部排序。 1、內(nèi)部排序： 就是將需要排序的數(shù)據(jù)都加載到內(nèi)存中，然后進(jìn)行排序。內(nèi)部排序又分為以下幾類： 2、外部排序： 內(nèi)部排序有個(gè)問題，假如現(xiàn)在要排序的數(shù)據(jù)有10億個(gè)，服務(wù)器內(nèi)存加載不了那么多的數(shù)據(jù)，那就得用外部排序了。外部排序就是先加載一部分，排完了再加載另外一部分，然后再合并。 二、常見的時(shí)間復(fù)雜度時(shí)間復(fù)雜度從低到高依次有： 接下來，就先看看大家最熟悉的冒泡排序和選擇排序。為了避免篇幅過長，其他六種排序中的每一種都會(huì)用一篇單獨(dú)的文章來介紹。 三、冒泡排序時(shí)間復(fù)雜度為O(n^2)。 1、排序思想： 從前往后遍歷待排序的序列，依次比較相鄰元素的值，如果逆序，就交換位置。 2、案例： 假如現(xiàn)有一個(gè)待排序列：3, 9, -1, 10, 20，現(xiàn)要用冒泡排序算法將其從小到大排列，過程如下： (1). 第一趟： - 比較3和9，發(fā)現(xiàn)3比9小且3在前面，所以不改變位置，結(jié)果是
3, 9, -1, 10, 20，同時(shí)兩個(gè)指針都后移一位； - 比較9和-1，交換它們的位置，結(jié)果是
3, -1, 9, 10, 20，同時(shí)兩個(gè)指針都后移一位； - 比較9和10，不發(fā)生交換，結(jié)果是
3, -1, 9, 10, 20，同時(shí)兩個(gè)指針都后移一位； - 比較10和20，不發(fā)生交換，結(jié)果是
3, -1, 9, 10, 20，同時(shí)兩個(gè)指針都后移一位；
一趟排序結(jié)束后，最大的數(shù)就排到最后去了。 (2). 第二趟： 經(jīng)過第一趟，其實(shí)最后面那個(gè)數(shù)就是最大了，第二趟要做的就是在前面的四個(gè)數(shù)中找到最大的，放在倒數(shù)第二個(gè)的位置。 - 比較3和-1，交換位置，結(jié)果是
-1, 3, 9, 10, 20，同時(shí)兩個(gè)指針都后移一位； - 比較3和9，不發(fā)生交換，結(jié)果是
-1, 3, 9, 10, 20，同時(shí)兩個(gè)指針都后移一位； - 比較9和10，不發(fā)生交換，結(jié)果是
-1, 3, 9, 10, 20，同時(shí)兩個(gè)指針都后移一位；
經(jīng)過第二趟，就將第二大的數(shù)排到了倒數(shù)第二位。 (3). 第三趟： - 比較-1和3，不發(fā)生交換，結(jié)果是
-1, 3, 9, 10, 20，同時(shí)兩個(gè)指針都后移一位； - 比較3和9，不發(fā)生交換，結(jié)果是
-1, 3, 9, 10, 20，同時(shí)兩個(gè)指針都后移一位；
經(jīng)過這一趟，就將9排到了倒數(shù)第三位。 (4). 第四趟： - 比較-1和3，不發(fā)生交換，結(jié)果是
-1, 3, 9, 10, 20，同時(shí)兩個(gè)指針都后移一位；
經(jīng)過這趟，排序就結(jié)束了。 通過這個(gè)案例可以發(fā)現(xiàn)，總共需要進(jìn)行元素個(gè)數(shù)減一次排序，并且每次比較的個(gè)數(shù)都在減少。而且，上面第二趟交換了3和-1的位置后，其實(shí)整個(gè)數(shù)組就已經(jīng)是有序的了，后面的步驟都不用執(zhí)行了。 3、代碼實(shí)現(xiàn)： public void sort(int[] arr) {
// 外層控制控制要排序幾趟
int temp = 0;
for(int i=0; i<arr.length-1; i++) {
boolean flag = false; // 如果某一趟中沒有一個(gè)元素發(fā)生交換，說明已經(jīng)有序了，flag用來標(biāo)識(shí)某一趟中是否發(fā)生過交換
// 比較arr[j]和arr[j+1]的大小，如逆序，則交換。
for(int j=0; j<arr.length-1-i; j++) {
if (arr[j] > arr[j+1]) {
temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
flag = true;
}
}
if (!flag) {
break;
}
}
}
四、選擇排序時(shí)間復(fù)雜度也是O(n^2)，但是經(jīng)測試，選擇排序速度會(huì)比冒泡排序更快。 1、排序思想： 第一趟，用arr[0]依次跟其他元素比較，如果比arr[0]更小，那就認(rèn)為該數(shù)最小，記住其下標(biāo)，讓其他元素跟該數(shù)比較，若又更小，那些又記住新的更小的那個(gè)數(shù)的下標(biāo)……第一趟完成后，就找到了最小的數(shù)，并讓它與arr[0]交換位置； 第二趟，用arr[1]跟其他元素比較，重復(fù)第一趟的步驟……
2、代碼實(shí)現(xiàn)： public static void sort(int[] arr) {
// 外層循環(huán)控制第幾趟比較
for(int i=0; i<arr.length-1; i++) {
int minNum = arr[i]; // 假定當(dāng)前元素是最小的
int minNumIndex = i; // 最小值的下標(biāo)
for(int j=i+1; j<arr.length; j++) {
if (arr[j] < minNum) {
// 如果arr[j]比之前認(rèn)為的最小值還小，就把它當(dāng)成新的最小值，并且記住下標(biāo)
minNum = arr[j];
minNumIndex = j;
}
}
// 一輪下來，交換arr[i]和最小值的位置
// 如果最小值索引minIndex就等于i，那就不用交換
if (minNumIndex != i) {
arr[minNumIndex] = arr[i];
arr[i] = minNum;
}
}
}
后續(xù)會(huì)有文章介紹其他六大排序算法，敬請(qǐng)期待。
|
