1. 排序的概念
排序： 所謂排序，就是使一串記錄，按照其中的某個或某些關鍵字的大小，遞增或遞減的排列起來的操作
穩(wěn)定性： 假定在待排序的記錄序列中，存在多個具有相同的關鍵字的記錄，若經過排序，這些記錄的相對次序保持不變，即在原序列中，r[i]=r[j]，且r[i]在r[j]之前，而在排序后的序列中，r[i]仍在r[j]之前，則稱這種排序算法是穩(wěn)定的；否則稱為不穩(wěn)定的
內部排序： 數據元素全部放在內存中的排序
外部排序： 數據元素太多不能同時放在內存中，根據排序過程的要求不能在內外存之間移動數據的排序
2. 常見排序算法的實現
2.1 插入排序
2.1.1基本思想
直接插入排序是一種簡單的插入排序法，其基本思想是：把待排序的記錄按其關鍵碼值的大小逐個插入到一個已經排好序的有序序列中，直到所有的記錄插入完為止，得到一個新的有序序列
2.1.2 直接插入排序
當插入第i(i>=1)個元素時，前面的array[0],array[1],…,array[i-1]已經排好序，此時用array[i]的排序碼與array[i-1],array[i-2],…的排序碼順序進行比較，找到插入位置即將array[i]插入，原來位置上的元素順序后移
public static void insertSort(int[] arr) {
for (int i = 1; i < arr.length; i++) {
int tmp = arr[i];
int j = i - 1;
while (j >= 0) {
if (arr[j] > tmp) {
arr[j + 1] = arr[j];
j--;
}else {
break;
}
}
arr[j + 1] = tmp;
}
}
直接插入排序的特性總結：
- 元素集合越接近有序，直接插入排序算法的時間效率越高
- 時間復雜度：O(N^2)
- 空間復雜度：O(1)，它是一種穩(wěn)定的排序算法
- 穩(wěn)定性：穩(wěn)定
2.1.3 希爾排序( 縮小增量排序 )
希爾排序法又稱縮小增量法。希爾排序法的基本思想是：先選定一個整數，把待排序文件中所有記錄分成多個組，所有距離為的記錄分在同一組內，并對每一組內的記錄進行排序。然后，取，重復上述分組和排序的工作。當到達=1時，所有記錄在統一組內排好序
public static void shellSort(int[] arr) {
int gap = arr.length;;
while (gap > 1) {
gap /= 2;
shell(arr, gap);
}
}
public static void shell(int[] arr, int gap) {
for (int i = gap; i < arr.length; i++) {
int j = i - gap;
int temp = arr[i];
while (j >= 0) {
if (arr[j] > temp) {
arr[j + gap] = arr[j];
j -= gap;
}else {
break;
}
}
arr[j + gap] = temp;
}
}
希爾排序的特性總結：
- 希爾排序是對直接插入排序的優(yōu)化。
- 當gap > 1時都是預排序，目的是讓數組更接近于有序。當gap == 1時，數組已經接近有序的了，這樣就會很快。這樣整體而言，可以達到優(yōu)化的效果。我們實現后可以進行性能測試的對比
- 希爾排序的時間復雜度不好計算，因為gap的取值方法很多，導致很難去計算，因此在好些書中給出的希爾排序的時間復雜度都不固定:
2.2 選擇排序
2.2.1基本思想
每一次從待排序的數據元素中選出最?。ɑ蜃畲螅┑囊粋€元素，存放在序列的起始位置，直到全部待排序的數據元素排完
2.2.2 直接選擇排序:
- 在元素集合array[i]–array[n-1]中選擇關鍵碼最大(小)的數據元素
- 若它不是這組元素中的最后一個(第一個)元素，則將它與這組元素中的最后一個（第一個）元素交換
- 在剩余的array[i]–array[n-2]（array[i+1]–array[n-1]）集合中，重復上述步驟，直到集合剩余1個元素
public static void selectSort(int[] arr) {
for (int i = 0; i < arr.length; i++) {
int minIndex = i;
for (int j = i + 1; j < arr.length; j++) {
if (arr[j] < arr[minIndex]) {
minIndex = j;
}
}
swap(arr, i, minIndex);
}
}
直接選擇排序的特性總結:
- 直接選擇排序思考非常好理解，但是效率不是很好。實際中很少使用
- 時間復雜度：O(N^2)
- 空間復雜度：O(1)
- 穩(wěn)定性：不穩(wěn)定
2.2.3 堆排序
堆排序(Heapsort)是指利用堆積樹（堆）這種數據結構所設計的一種排序算法，它是選擇排序的一種。它是通過堆來進行選擇數據。需要注意的是排升序要建大堆，排降序建小堆
public static void heapSort(int[] arr) {
createHeap(arr);
int end = arr.length - 1;
while (end > 0) {
swap(arr,0,end);
siftDown(arr,0,end);
end--;
}
}
private static void createHeap(int[] arr) {
for (int i = (arr.length-1-1) / 2; i >=0 ; i--) {
siftDown(arr,i,arr.length);
}
}
private static void siftDown(int[] arr,int parent,int len) {
int child = parent * 2 + 1;
while (child < len) {
if (child + 1 < len && arr[child] < arr[child+1]) {
child++;
}
if (arr[child] > arr[parent]) {
swap(arr,child,parent);
parent = child;
child = 2 * child +1;
}else {
break;
}
}
}
堆排序的特性總結:
- 堆排序使用堆來選數，效率就高了很多。
- 時間復雜度：O(N*logN)
- 空間復雜度：O(1)
- 穩(wěn)定性：不穩(wěn)定
2.3 交換排序
基本思想：所謂交換，就是根據序列中兩個記錄鍵值的比較結果來對換這兩個記錄在序列中的位置，交換排序的特點是：將鍵值較大的記錄向序列的尾部移動，鍵值較小的記錄向序列的前部移動
2.3.1冒泡排序
public static void bubbleSort(int[] array){
for (int i = 0; i < array.length - 1; i++) {
for (int j = 0; j < array.length - i - 1; j++) {
if (array[j] > array[j+1]) {
int temp = array[j];
array[j] = array[j+1];
array[j+1] = temp;
}
}
}
}
冒泡排序的特性總結:
- 冒泡排序是一種非常容易理解的排序
- 時間復雜度：O(N^2)
- 空間復雜度：O(1)
- 穩(wěn)定性：穩(wěn)定
2.3.2 快速排序
快速排序是Hoare于1962年提出的一種二叉樹結構的交換排序方法，其基本思想為：任取待排序元素序列中的某元素作為基準值，按照該排序碼將待排序集合分割成兩子序列，左子序列中所有元素均小于基準值，右子序列中所有元素均大于基準值，然后最左右子序列重復該過程，直到所有元素都排列在相應位置上為止
/**
*/
public static void quickSort(int[] arr) {
quick(arr, 0, arr.length - 1);
}
private static void quick(int[] arr, int start, int end) {
if (start >= end) {
return;
}
// 減少遞歸次數(數組趨于有序使用插入排序)
if (end - start <= 20) {
insert(arr, start, end);
return;
}
// 使基準左右兩邊更加平衡
int i = midThree(arr, start, end);
swap(arr, start, i);
int pivot = partition(arr, start, end);
quick(arr, start, pivot - 1);
quick(arr, pivot + 1, end);
}
/**
* 找基準 挖坑法
* @param arr
* @param left
* @param right
* @return
*/
public static int partition(int[] arr, int left, int right) {
int tmp = arr[left];
while (left < right) {
while (left < right && arr[right] >= tmp) {
right--;
}
arr[left] = arr[right];
while (left < right && arr[left] <= tmp) {
left++;
}
arr[right] = arr[left];
}
arr[left] = tmp;
return left;
}
/**
* hoare法
* @param arr
* @param left
* @param right
* @return
*/
public static int partition2(int[] arr, int left, int right) {
int tmp = arr[left];
int i = left;
while (left < right) {
while (left < right && arr[right] >= tmp) {
right--;
}
while (left < right && arr[left] <= tmp) {
left++;
}
swap(arr, left, right);
}
swap(arr, i, left);
return left;
}
/**
* 前后指針法
* @param arr
* @param left
* @param right
* @return
*/
public static int partition3(int[] arr, int left, int right) {
int prev = left - 1;
int cur = left;
while (cur < right){
if (arr[cur] < arr[right] && arr[++prev] != arr[cur]){
swap(arr,prev,cur);
}
cur++;
}
swap(arr,right,prev + 1);
return prev + 1;
}
/**
* 三數取中
* @param arr
* @param left
* @param right
* @return
*/
private static int midThree(int[] arr, int left, int right) {
int mid = (left + right) / 2;
if (arr[left] > arr[right]) {
if (arr[mid] < arr[right]) {
return right;
} else if (arr[mid] > arr[left]) {
return left;
}else {
return mid;
}
}else {
if (arr[mid] < arr[left]) {
return left;
} else if (arr[mid] > arr[right]) {
return right;
}else {
return mid;
}
}
}
public static void insert(int[] arr, int start, int end) {
for (int i = start + 1; i <= end; i++) {
int tmp = arr[i];
int j = i - 1;
while (j >= start) {
if (arr[j] > tmp) {
arr[j + 1] = arr[j];
j--;
}else {
break;
}
}
arr[j + 1] = tmp;
}
}
/**
* 非遞歸實現
* @param arr
*/
public static void quick(int[] arr) {
int left = 0;
int right = arr.length - 1;
int mid = midThree(arr, left, right);
Stack<Integer> stack = new Stack<>();
swap(arr, left, mid);
int partition = partition(arr, left, right);
if (partition > left + 1) {
stack.push(left);
stack.push(partition - 1);
}
if (partition < right - 1) {
stack.push(partition + 1);
stack.push(right);
}
while (!stack.isEmpty()) {
right = stack.pop();
left = stack.pop();
mid = midThree(arr, left, right);
swap(arr, left, mid);
partition = partition(arr, left, right);
if (partition > left + 1) {
stack.push(left);
stack.push(partition - 1);
}
if (partition < right - 1) {
stack.push(partition + 1);
stack.push(right);
}
}
}
快速排序總結:
- 快速排序整體的綜合性能和使用場景都是比較好的，所以才敢叫快速排序
- 時間復雜度：O(N*logN)
- 空間復雜度：O(logN)
- 穩(wěn)定性：不穩(wěn)定
2.4 歸并排序
2.4.1 基本思想
歸并排序（MERGE-SORT）是建立在歸并操作上的一種有效的排序算法,該算法是采用分治法（Divide andConquer）的一個非常典型的應用。將已有序的子序列合并，得到完全有序的序列；即先使每個子序列有序，再使子序列段間有序。若將兩個有序表合并成一個有序表，稱為二路歸并。 歸并排序核心步驟:
public static void mergeSort(int[] arr) {
mergeSortFun(arr, 0, arr.length - 1);
}
private static void mergeSortFun(int[] arr, int left, int right) {
if (left >= right) {
return;
}
int mid = (left + right) / 2;
mergeSortFun(arr, left, mid);
mergeSortFun(arr, mid + 1, right);
merge(arr, left, right, mid);
}
private static void merge(int[] arr, int left, int right, int mid) {
int s1 = left;
int s2 = mid + 1;
int[] tmp = new int[right - left + 1];
int k = 0;
while (s1 <= mid && s2 <= right) {
if (arr[s1] > arr[s2]) {
tmp[k++] = arr[s2++];
}else {
tmp[k++] = arr[s1++];
}
}
while (s1 <= mid) {
tmp[k++] = arr[s1++];
}
while (s2 <= right) {
tmp[k++] = arr[s2++];
}
for (int i = 0; i < tmp.length; i++) {
arr[i + left] = tmp[i];
}
}
歸并排序總結
- 歸并的缺點在于需要O(N)的空間復雜度，歸并排序的思考更多的是解決在磁盤中的外排序問題。
- 時間復雜度：O(N*logN)
- 空間復雜度：O(N)
- 穩(wěn)定性：穩(wěn)定
2.4.2 海量數據的排序問題
外部排序：排序過程需要在磁盤等外部存儲進行的排序
前提：內存只有 1G，需要排序的數據有 100G
因為內存中因為無法把所有數據全部放下，所以需要外部排序，而歸并排序是最常用的外部排序文章來源：http://www.zghlxwxcb.cn/news/detail-729052.html
- 先把文件切分成 200 份，每個 512 M
- 分別對 512 M 排序，因為內存已經可以放的下，所以任意排序方式都可以
- 進行 2路歸并，同時對 200 份有序文件做歸并過程，最終結果就有序了
3. 排序算法復雜度及穩(wěn)定性分析
文章來源地址http://www.zghlxwxcb.cn/news/detail-729052.html
| 排序方法 | 最好 | 平均 | 最壞 | 空間復雜度 | 穩(wěn)定性 |
|---|---|---|---|---|---|
| 冒泡排序 | O(n) | O(n^2) | O(n^2) | O(1) | 穩(wěn)定 |
| 插入排序 | O(n) | O(n^2) | O(n^2) | O(1) | 穩(wěn)定 |
| 選擇排序 | O(n^2) | O(n^2) | O(n^2) | O(1) | 不穩(wěn)定 |
| 希爾排序 | O(n) | O(n^1.3) | O(n^2) | O(1) | 不穩(wěn)定 |
| 堆排序 | O(n * log(n)) | O(n * log(n)) | O(n * log(n)) | O(1) | 不穩(wěn)定 |
| 快速排序 | O(n * log(n)) | O(n * log(n)) | O(n^2) | O(log(n)) ~ O(n) | 不穩(wěn)定 |
| 歸并排序 | O(n * log(n)) | O(n * log(n)) | O(n * log(n)) | O(n) | 穩(wěn)定 |
到了這里，關于常見的幾種排序方式的文章就介紹完了。如果您還想了解更多內容，請在右上角搜索TOY模板網以前的文章或繼續(xù)瀏覽下面的相關文章，希望大家以后多多支持TOY模板網！
