快速排序
步驟
- 從列表選出一個基準值 pivot
- 重新排列數(shù)組，所有比基準值小的放在基準值左邊，所有比基準值大的放在基準值右邊。
- 遞歸把基準值左右兩邊的數(shù)列排序。
時間復雜度O(nlogn)
最壞的情況：序列已經(jīng)是升序排序，需要比較n(n-1)/2次，為O(n^2)
最好的情況：每次劃分都是正好兩半 T(n) <= 2T(n/2)+O(n) —> T(n) = O(nlogn)
空間復雜度O(nlogn)：由于是遞歸調(diào)用，空間復雜度為O(nlogn)
快速排序是不穩(wěn)定的，時間復雜度O(nlogn)，不穩(wěn)定發(fā)生在中樞元素和a[j]，中樞元素左邊的元素可能和右邊的元素相等，當中樞元素和其交換時，破壞了穩(wěn)定性
public static void quickSort(int[] arr, int left, int right) {
if (left >= right) {
return;
}
int pivot = partition(arr, left, right);
quickSort(arr, left, pivot - 1);
quickSort(arr, pivot + 1, right);
}
public static int partition(int[] arr, int low, int high) {
int pivot = arr[low];
while (low < high) {
while (low < high && arr[high] >= pivot)
high--;
arr[low] = arr[high];
while (low < high && arr[low] <= pivot)
low++;
arr[high] = arr[low];
}
arr[low] = pivot;
return low;
}
冒泡排序
相鄰兩個元素進行交換，把大的元素浮到最上面
時間復雜度O(n^2)：最外層for執(zhí)行n次，內(nèi)層循環(huán)j從0～i-1，i從n-1～1，復雜度為n*(n-1)/2，
空間復雜度O(1)：只需要一個temp位置交換
穩(wěn)定：比較兩個相鄰元素并進行交換，如果相等，則不會交換，穩(wěn)定性沒有被破壞。
public void bubbleSort(int[] arr) {
if(arr == null || arr.length == 0)
return ;
for(int i=0;i<arr.length-1;i++) {
for(int j=0;j<arr.length-i-1;j++) {
if (arr[j]>arr[j+1]) {
int temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
}
}
}
}
選擇排序
一次排序后把最小的元素放在最前面
時間復雜度O(n^2)：比較次數(shù)和初始狀態(tài)無關(guān)，為n(n-1)/2，最好，最壞和平均情況均為O(n2)
空間復雜度O(1)：
不穩(wěn)定，不穩(wěn)定發(fā)生在最小的元素當前元素交換時，如果當前元素在最小元素前面，并且比和當前元素相等時，交換之后穩(wěn)定性就被破壞
public static void selectSort(int[] arr) {
if(arr == null || arr.length == 0)
return ;
int minIndex = 0;
for(int i=0;i<arr.length-1;i++) {//比較n-1次
minIndex = I;
for (int j = i+1; j < arr.length; j++) {//從i+1開始比較，minIndex默認為I
if (arr[j]<arr[minIndex]) {
minIndex = j;
}
}
if (minIndex!=i) {
swap(arr, i, minIndex);//minIndex不為i，說明找到更小的，交換
}
}
}
插入排序
在一個已經(jīng)排好序的序列中，為下一個找到一個合適的插入位置
時間復雜度O(n^2)：外層for共執(zhí)行arr.length-2次，內(nèi)層循環(huán)最少執(zhí)行1次，最多執(zhí)行index次，算法復雜度n*(n-1)/2
空間復雜度O(1)：只需要一個位置key用于交換
穩(wěn)定：插入排序是在已經(jīng)有序的小序列中進行插入一個元素，即使遇到相等的元素，也是插入在其后面，穩(wěn)定性沒有被破壞
public static void insertSort(int[] arr) {
if (arr == null || arr.length == 0)
return;
for (int i = 1; i < arr.length; i++) {// 假設(shè)第一個位置正確，要往后移，必須假設(shè)第一個
int j = I;
int target = arr[i];// 待插入
while (j > 0 && target < arr[j - 1]) {// 往后移
arr[j] = arr[j - 1];
j--;
}
arr[j] = target;
}
}
希爾排序
思想：分組插入排序，將整個待排序序列分割成若干個子序列，并分別進行插入排序，然后再縮小增量繼續(xù)排序，當增量足夠小時，再對全體元素進行直接插入排序。
時間復雜度O(nlogn)：
時間復雜度依賴于增量序列
最好的情況：序列是升序序列，需要比較n次，后移賦值操作為0次，O(n)
最壞的情況：序列的降序序列，O(nlogn)
空間復雜度O(1)：只需要一個位置置換
public static void shellSort(int[] arr) {
int i, j, gap;
for (gap = arr.length / 2; gap > 0; gap /= 2) {
for (i = gap; i < arr.length; i++) {
for (j = i - gap; j >= 0 && arr[j] > arr[j + gap]; j -= gap)
swap(arr, j, j + gap);
}
}
}
歸并排序
合并兩個有序的子數(shù)組
思想：遞歸分治+歸并
把待排序列看成兩個有序序列，然后合并兩個子序列。倒著看，兩兩合并，四四合并。。。最終形成有序序列。
時間復雜度O(nlogn)：歸并排序是一種非“就地”排序，需要和待排序序列一樣多的輔助空間，故歸并排序的缺點是所需額外空間多，對長度為n的數(shù)組，需要進行l(wèi)ogn趟二路歸并，每趟歸并的時間為O(n)，故其時間復雜度無論在最好還是最壞情況下都是O(nlogn)
空間復雜度O(n)：排序時需要和待排序序列一樣的空間，空間復雜度為O(n)
穩(wěn)定：歸并排序是把序列遞歸的分成短序列，遞歸出口是只有一個元素或者2個元素短有序序列，然后把各個有序序列合并成有序的長序列，不斷合并知道原序列全部排好序。在短序列中，即使兩個元素相等也不會交換，因此穩(wěn)定性沒有被破壞。
使用場合
public static void mergeArray(int[] arr, int left, int mid, int right) {
if (arr == null || arr.length == 0)
return;
int[] temp = new int[right-left+1];
int i = left, j = mid + 1;
int k = 0;
// 二路歸并
while (i < mid && j <= right) {
if (arr[i] <= arr[j]) {
temp[k++] = arr[i++];
} else {
temp[k++] = arr[j++];
}
}
// 處理子數(shù)組中剩余元素
while (i <= mid) {
temp[k++] = arr[i++];
}
while (j <= right) {
temp[k++] = arr[j++];
}
// 從臨時數(shù)組中拷貝到目標數(shù)組
for (i = 0; i < temp.length; i++) {
arr[left + i] = temp[I];
}
}
public static void mergeSort(int[] arr, int left, int right) {
if (left < right) {
int mid = (left + right) / 2;
// 歸并排序使得左邊序列有序
mergeSort(arr, left, mid);
// 歸并排序使得右邊序列有序
mergeSort(arr, mid + 1, right);
// 合并兩個有序序列
mergeArray(arr, left, mid, right);
}
}
堆排序
時間復雜度O(nlogn)：最好，最壞，平均均為O(nlogn)
空間復雜度O(1)
思想：
堆（二叉堆）：一棵完全二叉樹
- 最大堆調(diào)整：將堆末端子節(jié)點作調(diào)整，使得子節(jié)點永遠小于父節(jié)點
- 創(chuàng)建最大堆：將堆所有數(shù)據(jù)重新排序，使其成為最大堆
- 堆排序：移除位于第一個數(shù)據(jù)的根節(jié)點，并作最大堆調(diào)整堆遞歸運算，將最大的元素從堆中分離
parent(i) = floor((i-1)/2)，i的父節(jié)點下標
left(i) = 2i+1，i的左子節(jié)點下標
right(i) = 2(i+1)，i的右子節(jié)點下標
不穩(wěn)定：堆和其子節(jié)點（堆，左節(jié)點，右節(jié)點）交換不會破壞穩(wěn)定性，堆頂元素移除時，父節(jié)點和某個元素交換，剛好該元素后面有相同的元素，就會破壞穩(wěn)定性。
public static void heapSort(int[] arr) {
int len = arr.length - 1;
int beginIndex = (len - 1) / 2;// 第一個非葉子節(jié)點
// 將數(shù)組堆化
for (int i = beginIndex; i >= 0; i--) {
maxHeapify(arr, i, len);
}
// 對堆化數(shù)組排序，每次都移出最頂層節(jié)點arr[0]，與尾部節(jié)點位置調(diào)換，同時遍歷長度-1，
// 然后從新調(diào)整被換到根節(jié)點末尾都元素，使其符合堆堆特性，直至未排序堆堆長度未0
for (int j = len; j >= 0; j--) {
swap(arr, 0, j);
maxHeapify(arr, 0, j - 1);
}
}
private static void maxHeapify(int[] arr, int index, int len) {
int li = (index * 2) + 1;// 左子節(jié)點索引
int ri = 2 * (index + 1);// 右子節(jié)點索引
int cMax = li;// 子節(jié)點值最大索引，默認左子節(jié)點
if (li > len)
return;// 左子節(jié)點索引超出計算范圍，直接返回
if (ri <= len && arr[ri] > arr[li])
cMax = ri;// 先判斷左右子節(jié)點哪個大
if (arr[cMax] > arr[index]) {
swap(arr, cMax, index);// 如果父節(jié)點被子節(jié)點調(diào)換
maxHeapify(arr, cMax, len);// 則需要繼續(xù)判斷換下后堆父節(jié)點是否符合堆堆性質(zhì)
}
}
不穩(wěn)定排序：選擇排序，快速排序，希爾排序，堆排序
穩(wěn)定排序：冒泡排序，插入排序，歸并排序，基數(shù)排序
