目錄
1.1冒泡排序
1. 算法步驟
?3.什么時候最快
4. 什么時候最慢
5.代碼實現(xiàn)
1.2選擇排序
1. 算法步驟
?2. 動圖演示
3.代碼實現(xiàn)
?1.3 插入排序
1. 算法步驟
2. 動圖演示
3. 算法實現(xiàn)
1.4 希爾排序
1. 算法步驟
2. 動圖演示
?3.代碼實現(xiàn)
1.5 歸并排序
1. 算法步驟
?2. 動圖演示
?3.代碼實現(xiàn)
1.1冒泡排序
? 冒泡排序（Bubble Sort）也是一種簡單直觀的排序算法。它重復(fù)地走訪過要排序的數(shù)列，一次比較兩個元素，如果他們的順序錯誤就把他們交換過來。走訪數(shù)列的工作是重復(fù)地進行直到?jīng)]有再需要交換，也就是說該數(shù)列已經(jīng)排序完成。
1. 算法步驟
- 比較相鄰的元素。如果第一個比第二個大，就交換他們兩個。
- 對每一對相鄰元素作同樣的工作，從開始第一對到結(jié)尾的最后一對。這步做完后，最后的元素會是最大的數(shù)。
- 針對所有的元素重復(fù)以上的步驟，除了最后一個。
- 持續(xù)每次對越來越少的元素重復(fù)上面的步驟，直到?jīng)]有任何一對數(shù)字需要比較。
?
?
?3.什么時候最快
當(dāng)輸入的數(shù)據(jù)已經(jīng)是正序時。
4. 什么時候最慢
當(dāng)輸入的數(shù)據(jù)是反序時
5.代碼實現(xiàn)
?
public class BubbleSort implements IArraySort {
@Override
public int[] sort(int[] sourceArray) throws Exception {
// 對 arr 進行拷貝，不改變參數(shù)內(nèi)容
int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);
for (int i = 1; i < arr.length; i++) {
// 設(shè)定一個標(biāo)記，若為true，則表示此次循環(huán)沒有進行交換，也就是待排序列已經(jīng)有序，排序已經(jīng)完成。
boolean flag = true;
for (int j = 0; j < arr.length - i; j++) {
if (arr[j] > arr[j + 1]) {
int tmp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = tmp;
flag = false;
}
}
if (flag) {
break;
}
}
return arr;
}
}1.2選擇排序
選擇排序是一種簡單直觀的排序算法，無論什么數(shù)據(jù)進去都是 O(n2) 的時間復(fù)雜度。
1. 算法步驟
- 首先在未排序序列中找到最?。ù螅┰兀娣诺脚判蛐蛄械钠鹗嘉恢?。
- 再從剩余未排序元素中繼續(xù)尋找最小（大）元素，然后放到已排序序列的末尾。
- 重復(fù)第二步，直到所有元素均排序完畢。
?2. 動圖演示
3.代碼實現(xiàn)
public class SelectionSort implements IArraySort {
@Override
public int[] sort(int[] sourceArray) throws Exception {
int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);
// 總共要經(jīng)過 N-1 輪比較
for (int i = 0; i < arr.length - 1; i++) {
int min = i;
// 每輪需要比較的次數(shù) N-i
for (int j = i + 1; j < arr.length; j++) {
if (arr[j] < arr[min]) {
// 記錄目前能找到的最小值元素的下標(biāo)
min = j;
}
}
// 將找到的最小值和i位置所在的值進行交換
if (i != min) {
int tmp = arr[i];
arr[i] = arr[min];
arr[min] = tmp;
}
}
return arr;
}
}?1.3 插入排序
插入排序是一種最簡單直觀的排序算法，它的工作原理是通過構(gòu)建有序序列，對于未排序數(shù)據(jù)，在已排序序列中從后向前掃描，找到相應(yīng)位置并插入。
插入排序和冒泡排序一樣，也有一種優(yōu)化算法，叫做拆半插入。
1. 算法步驟
- 將第一待排序序列第一個元素看做一個有序序列，把第二個元素到最后一個元素當(dāng)成是未排序序列。
- 從頭到尾依次掃描未排序序列，將掃描到的每個元素插入有序序列的適當(dāng)位置。（如果待插入的元素與有序序列中的某個元素相等，則將待插入元素插入到相等元素的后面。）
2. 動圖演示
3. 算法實現(xiàn)
public class InsertSort implements IArraySort {
@Override
public int[] sort(int[] sourceArray) throws Exception {
// 對 arr 進行拷貝，不改變參數(shù)內(nèi)容
int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);
// 從下標(biāo)為1的元素開始選擇合適的位置插入，因為下標(biāo)為0的只有一個元素，默認(rèn)是有序的
for (int i = 1; i < arr.length; i++) {
// 記錄要插入的數(shù)據(jù)
int tmp = arr[i];
// 從已經(jīng)排序的序列最右邊的開始比較，找到比其小的數(shù)
int j = i;
while (j > 0 && tmp < arr[j - 1]) {
arr[j] = arr[j - 1];
j--;
}
// 存在比其小的數(shù)，插入
if (j != i) {
arr[j] = tmp;
}
}
return arr;
}
}1.4 希爾排序
希爾排序，也稱遞減增量排序算法，是插入排序的一種更高效的改進版本。但希爾排序是非穩(wěn)定排序算法。
希爾排序是基于插入排序的以下兩點性質(zhì)而提出改進方法的：
- 插入排序在對幾乎已經(jīng)排好序的數(shù)據(jù)操作時，效率高，即可以達到線性排序的效率；
- 但插入排序一般來說是低效的，因為插入排序每次只能將數(shù)據(jù)移動一位；
希爾排序的基本思想是：先將整個待排序的記錄序列分割成為若干子序列分別進行直接插入排序，待整個序列中的記錄"基本有序"時，再對全體記錄進行依次直接插入排序。
1. 算法步驟
- 選擇一個增量序列 t1，t2，……，tk，其中 ti > tj, tk = 1；
- 按增量序列個數(shù) k，對序列進行 k 趟排序；
- 每趟排序，根據(jù)對應(yīng)的增量 ti，將待排序列分割成若干長度為 m 的子序列，分別對各子表進行直接插入排序。僅增量因子為 1 時，整個序列作為一個表來處理，表長度即為整個序列的長度。
2. 動圖演示
?
?3.代碼實現(xiàn)
public static void shellSort(int[] arr) {
int length = arr.length;
int temp;
for (int step = length / 2; step >= 1; step /= 2) {
for (int i = step; i < length; i++) {
temp = arr[i];
int j = i - step;
while (j >= 0 && arr[j] > temp) {
arr[j + step] = arr[j];
j -= step;
}
arr[j + step] = temp;
}
}
}1.5 歸并排序
歸并排序（Merge sort）是建立在歸并操作上的一種有效的排序算法。該算法是采用分治法（Divide and Conquer）的一個非常典型的應(yīng)用。
作為一種典型的分而治之思想的算法應(yīng)用，歸并排序的實現(xiàn)由兩種方法：文章來源：http://www.zghlxwxcb.cn/news/detail-781099.html
- 自上而下的遞歸（所有遞歸的方法都可以用迭代重寫，所以就有了第 2 種方法）；
- 自下而上的迭代；
1. 算法步驟
- 申請空間，使其大小為兩個已經(jīng)排序序列之和，該空間用來存放合并后的序列；
- 設(shè)定兩個指針，最初位置分別為兩個已經(jīng)排序序列的起始位置；
- 比較兩個指針?biāo)赶虻脑兀x擇相對小的元素放入到合并空間，并移動指針到下一位置；
- 重復(fù)步驟 3 直到某一指針達到序列尾；
- 將另一序列剩下的所有元素直接復(fù)制到合并序列尾。
?2. 動圖演示
文章來源地址http://www.zghlxwxcb.cn/news/detail-781099.html
?3.代碼實現(xiàn)
public class MergeSort implements IArraySort {
@Override
public int[] sort(int[] sourceArray) throws Exception {
// 對 arr 進行拷貝，不改變參數(shù)內(nèi)容
int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);
if (arr.length < 2) {
return arr;
}
int middle = (int) Math.floor(arr.length / 2);
int[] left = Arrays.copyOfRange(arr, 0, middle);
int[] right = Arrays.copyOfRange(arr, middle, arr.length);
return merge(sort(left), sort(right));
}
protected int[] merge(int[] left, int[] right) {
int[] result = new int[left.length + right.length];
int i = 0;
while (left.length > 0 && right.length > 0) {
if (left[0] <= right[0]) {
result[i++] = left[0];
left = Arrays.copyOfRange(left, 1, left.length);
} else {
result[i++] = right[0];
right = Arrays.copyOfRange(right, 1, right.length);
}
}
while (left.length > 0) {
result[i++] = left[0];
left = Arrays.copyOfRange(left, 1, left.length);
}
while (right.length > 0) {
result[i++] = right[0];
right = Arrays.copyOfRange(right, 1, right.length);
}
return result;
}
}到了這里，關(guān)于十大經(jīng)典排序算法(上)的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
