穩(wěn)定的排序
| 算法 | 時間復雜度 | 空間復雜度 |
|---|---|---|
| 冒泡排序 | 最差、平均都是O(n^2)，最好是O(n) | 1 |
| 插入排序 | 最差、平均都是O(n^2)值桩，最好是O(n) | 1 |
| 歸并排序 | 最差豪椿、平均和最好都是O(nlog n) | O(n) |
不穩(wěn)定的排序
| 算法 | 時間復雜度 | 空間復雜度 |
|---|---|---|
| 選擇排序 | 最差、平均都是O(n^2) | 1 |
| 希爾排序 | O(nlog n) | 1 |
| 快速排序 | 平均是O(nlog n)搭盾，最壞情況下是O(n^2) | O(log n) |
冒泡排序
/**
* 冒泡排序原理：從頭部開始，兩兩對比澜建，并交換調整更大（小）值在數(shù)組中的位置炕舵，
* 把未有序部分中最大（小）值移動到有序部分的頭部咽筋。 * 就像“冒泡”一樣徊件，把無序部
分中的最大（小）值庇忌，移動到有序部分舞箍。
*
* @author Affy
* @date 2018-09-20
*/
public class BubbleSort {
public static void bubbleSort(int[] source) {
int unSortIndex = 0;
int sortHeadIndex = source.length - 1;
System.out.print("before sort: ");
for (int i = 0; i < source.length; i++) {
System.out.printf("%d ", source[i]);
}
boolean exchange = false;
int times = 0;
for (int high = sortHeadIndex; high > unSortIndex; high--) {
exchange = false;
times++;
//兩兩，把更大的值往后“冒”皆疹，直到有序序列的頭部位置
for (int low = 0; low < sortHeadIndex; low++) {
if (source[low] > source[low + 1]) {
int temp = source[low];
source[low] = source[low + 1];
source[low + 1] = temp;
exchange = true;
}
}
//如果存在某一次排序沒有發(fā)生交換疏橄，證明無序區(qū)中所有元素都有序，可以提前終止算法了
if (!exchange) {
break;
}
}
System.out.print("\n第" + times + "趟完成排序" + "\nafter sort: ");
for (int i = 0; i < source.length; i++) {
System.out.printf("%d ", source[i]);
}
}
public static void main(String[] args) {
int[] source = {44, 5, 9, 7, 3, 10, 4, 6, 1, 7, 12, 51};
bubbleSort(source);
}
}
- 算法的最好時間復雜度
若文件的初始狀態(tài)是有序的，則一次掃描就可完成排序捎迫，則比較次數(shù)C=n-1晃酒，移動次數(shù)M=0；也就是時間復雜度為O(n)窄绒。 - 算法的最壞時間復雜度
若文件的初始狀態(tài)是逆序贝次，則需要進行n-1次排序。每次排序要進行n-i次關鍵字的比較（1<= i <= n-1）,每次比較都必須移動記錄三次來達到交換記錄位置彰导。此時比較次數(shù)C=n(n-1)/2 = O(n^2 )蛔翅，交換次數(shù)M=3n(n-1)/2 = O( n^2 )。也就是時間復雜度為O(n^2)位谋。
選擇排序
/**
* 每趟排序山析，從未排序序列中選擇最小（大）值掏父，放到有序序列的末尾
*
* @author Affy
* @date 2018-09-21
*/
public class SelectSort {
public static void selectSort(int[] source) {
System.out.print("before sort: ");
for (int i = 0; i < source.length; i++) {
System.out.printf("%d ", source[i]);
}
for (int low = 0; low < source.length - 1; low++) {
//每次遍歷笋轨，找到未排序隊列中的最小值，并標記其下標
int minimumIndex = low;
for (int high = low + 1; high < source.length; high++) {
if (source[minimumIndex] > source[high]) {
minimumIndex = high;
}
}
if (minimumIndex != low) {
int temp = source[low];
source[low] = source[minimumIndex];
source[minimumIndex] = temp;
}
}
System.out.print("\nafter sort: ");
for (int i = 0; i < source.length; i++) {
System.out.printf("%d ", source[i]);
}
}
public static void main(String[] args) {
int[] source = {44, 5, 9, 7, 3, 10, 4, 6, 1, 7, 12, 51};
selectSort(source);
}
}
選擇排序的交換操作介于0和(n-1)次之間赊淑；比較操作為n(n-1)/2次之間爵政；賦值操作介于0和3(n-1)次之間；平均復雜度為O(n^2)
插入排序
/**
* <li>從第一個元素開始陶缺，該元素可以認為已經被排序</li>
* <li>取出下一個元素钾挟，在有序序列中從后往前掃描</li>
* <li>如果取出的新元素比當前元素小，則將當前元素移動到下一位置</li>
* <li>重復上一步饱岸，直到新元素小于或等于前一個元素等龙，記錄該位置，并將新元素插入到該位置</li>
*
* @author Affy
* @date 2018-09-21
*/
public class InsertSort {
public static void insertSourt(int[] source) {
System.out.print("before sort: ");
for (int i = 0; i < source.length; i++) {
System.out.printf("%d ", source[i]);
}
for (int low = 0; low < source.length - 1; low++) {
//取出有序隊列末尾的后一個元素伶贰，從后往前遍歷。如果比當前元素小罐栈，則將當前元素移動一個位置(其實就是交換兩元素)
for (int high = low + 1; high > 0 && source[high] < source[high - 1]; high--) {
int temp = source[high];
source[high] = source[high-1];
source[high-1] = temp;
}
}
System.out.print("\nafter sort: ");
for (int i = 0; i < source.length; i++) {
System.out.printf("%d ", source[i]);
}
}
public static void main(String[] args) {
int[] source = {44, 5, 9, 7, 3, 10, 4, 6, 1, 7, 12, 51};
insertSourt(source);
}
}
如果目標是升序排列，那么在最好和最壞的情況下：
- 最好：目標序列已經是升序荠诬。在這種情況下柑贞，只需要n-1次比較钧嘶。因此復雜度是O(n)。
- 最壞：目標序列是降序空盼。此時新荤，共需要進行n(n-1)/2次比較苛骨，賦值操作時比較次數(shù)加上n-1次痒芝。因此復雜度是O(n ^ 2)
平均來說，插入排序算法復雜度為O(n^2)校哎。因此不適合對于數(shù)據(jù)量比較大的排序應用闷哆。但是抱怔，如果量級小于千時屈留，那么插入排序還是一個不錯的選擇测蘑。
希爾排序
shell排序分組
可參考：圖解排序之希爾排序
package com.affy.testapp;
/**
* 希爾排序是把記錄按下標的一定增量分組勇蝙，對每組使用直接插入排序算法排序味混；隨著增量逐漸減少翁锡，
* 每組包含的關鍵詞越來越多夕土，當增量減至1時，整個文件恰被分成一組荒适，算法便終止
*
* @author Affy
* @date 2018-09-25
*/
public class ShellSort {
public static void shellSort(int[] source, int gap) {
System.out.print("\nbefore sort: ");
for (int i = 0; i < source.length; i++) {
System.out.printf("%d ", source[i]);
}
int high, low;
//從第一個間隔開始刀诬，依次對source[gap]...source[n]進行處理陕壹，每次比較都取source[high-gap],這樣就能確保覆蓋到每個元素
for (low = gap; low < source.length; low++) {
for (high = low; high - gap >= 0 && source[high - gap] > source[high]; high -= gap) {
int temp = source[high];
source[high] = source[high - gap];
source[high - gap] = temp;
}
}
System.out.print("\nafter sort: ");
for (int i = 0; i < source.length; i++) {
System.out.printf("%d ", source[i]);
}
}
public static void main(String[] args) {
int[] source = {44, 5, 9, 7, 3, 10, 4, 6, 1, 7, 12, 51};
int increment = source.length;
do {
increment /= 2;
shellSort(source, increment);
} while (increment > 0);
}
}
快速排序
1
2
3
4
5
6
7
8
總時序.jpg
/**
* 快排采用了分治法的策略進行排序
* <p>分治法：將原問題分解為若干規(guī)模更小但結構與原問題相似的子問題，
遞歸地解這些子問題毕匀，然后將這些子問題的解組合為原問題的解</p>
* <p>
* 快排基本思想：
* <ol>
* <li>分解癌别。選取基準展姐，使得基準左邊為小于或等于基準值，右邊大于或等于基準值</li>
* <li>求解教馆。遞歸調用快排對左右子區(qū)間R[low,pivotPos-1]和R[pivotPos+1,high]進行排序</li>
* <li>組合活玲。上一步做完之后，其實左右子區(qū)間已經有序镀钓，故無需做什么</li>
* </ol>
* </p>
*
* @author Affy
* @date 2018-09-26
*/
public class QuickSort {
private static void quickSort(int[] source, int low, int high) {
int pivot;//基準位置的記錄
if (low < high) {
int i = low;
int j = high;
pivot = source[i];
while (i < j) {
//從高處往左遍歷丁溅，直到找到第一個關鍵字小于pivot的記錄source[j]
while (j > i && source[j] >= pivot) {
j--;
}
//接著從i開始，從低處往右遍歷箱季，直到找到第一個關鍵字大于pivot的記錄source[i]藏雏。
while (i < j && source[i] <= pivot) {
i++;
}
//此時可交換source[i]和source[j]
if (i < j) {
source[i] = source[i] ^ source[j];
source[j] = source[i] ^ source[j];
source[i] = source[i] ^ source[j];
}
}
//當i == j時掘殴，i就是需要的基準位置粟誓，它的左邊小于它鹰服，右邊大于它,交換source[low]和source[i]
source[low] = source[i];
source[i] = pivot;
quickSort(source, low, i - 1);
quickSort(source, i + 1, high);
}
}
public static void main(String[] args) {
int[] source = {44, 5, 9, 7, 3, 10, 4, 6, 1, 7, 12, 51};
System.out.print("before sort: ");
for (int i = 0; i < source.length; i++) {
System.out.printf("%d ", source[i]);
}
quickSort(source, 0, source.length - 1);
System.out.print("\nafter sort: ");
for (int i = 0; i < source.length; i++) {
System.out.printf("%d ", source[i]);
}
}
}
這里交換操作用了亦或操作的小技巧悲酷，可參考：https://blog.csdn.net/heathyhuhu/article/details/12744407
歸并排序
分治
合并
圖片出處
/**
* 歸并排序笼踩。使用分割的方法將無序的序列分成一個一個已經排好序的子序列嚎于，
* 然后利用歸并的方法將一個個子序列合并成排好序的序列挟冠。 每次分割的時候知染，
* 首先分成兩份，然后再把2份分成4份嫌吠，一次分割直到分割成一個一個數(shù)據(jù)辫诅。
*
* @author Affy
* @date 2018-09-26
*/
public class MergeSort {
static void mergeSort(int[] source, int start, int end) {
if (start < end) {
int mid = (start + end) / 2;
//分組炕矮，不斷遞歸直到子序列只包含一個元素
mergeSort(source, start, mid);
mergeSort(source, mid + 1, end);
//合并
merge(source, start, mid, mid + 1, end);
}
}
static void merge(int[] source, int start1, int end1, int start2, int end2) {
//新建和兩個需要合并的數(shù)組大小一樣的臨時數(shù)組存放合并結果
int[] temp = new int[end2 - start1 + 1];
int i = start1, j = start2, k = 0;
//合并兩個數(shù)組，按照從小到大的順序排列
while (i <= end1 && j <= end2) {
if (source[i] < source[j]) {
temp[k++] = source[i++];
} else {
temp[k++] = source[j++];
}
}
//剩余元素存放
while (i <= end1) {
temp[k++] = source[i++];
}
while (j <= end2) {
temp[k++] = source[j++];
}
//將臨時數(shù)組替換到原數(shù)組
k = 0;
for (i = start1; i <= end2; i++) {
source[i] = temp[k++];
}
}
public static void main(String[] args) {
int[] source = {44, 5, 9, 7, 3, 10, 4, 6, 1, 7, 12, 51};
System.out.print("before sort: ");
for (int i = 0; i < source.length; i++) {
System.out.printf("%d ", source[i]);
}
mergeSort(source, 0, source.length - 1);
System.out.print("\nafter sort: ");
for (int i = 0; i < source.length; i++) {
System.out.printf("%d ", source[i]);
}
}
}
