- 基本排序：插入痒谴，選擇，冒泡
- 三大排序：歸并铡羡，快速积蔚，堆排
1甘磨、歸并排序 -- 時(shí)間復(fù)雜度O(N*logN)牡拇，空間復(fù)雜度O(N)
思路：遞歸方法，本質(zhì)是壓棧出棧的過(guò)程螟够，關(guān)鍵點(diǎn)是找出遞歸的basecase读慎，即問(wèn)題劃分到不能再往下劃分的點(diǎn)漱贱，再將排好序的兩部分合并即可
// 非遞歸方法，每相鄰2個(gè)數(shù)排序夭委，再下一層排序饱亿，k值每次*2,即可
public class MergeSort(){
public static void mergeSort(int[] arr){
if(arr == null || arr.length<2){
return;
}
mergeSort(arr, 0, arr.length-1);
}
public static void mergeSort(int[] arr, int left, int right){
int mid = left + ((right-1)>>1)
mergeSort(arr, left, mid);
mergeSort(arr, mid+1, right);
merge(arr, left, mid, right);
}
public static void merge(int[] arr, int left, int mid, int right){
int[] tmp = new int[right-left+1];
int i = 0;
int p1 = left;
int right = mid + 1;
while(p1<=mid && p2<=right){
tmp[i++] = arr[p1] < arr[p2] : arr[p1++] ? arr[p2++];
}
while(p1<=mid){
tmp[i++] = arr[p1++];
}
while(p2<=right){
tmp[i++] = arr[p2++];
}
for(i=0; i<tmp.lenth; i++){
arr[left+i] = tmp[i];
}
}
}
時(shí)間復(fù)雜度：T(N) = T(N/2) + T(N/2) + O(N)，可利用master公式得到N*logN
2闰靴、快速排序 -- 時(shí)間復(fù)雜度O(N*logN)彪笼，空間復(fù)雜度O(logN)
思路：先設(shè)定一個(gè)小于區(qū)，對(duì)于每一個(gè)從左到右的數(shù)蚂且，與最后的值比較配猫，若小于比較值，則小于區(qū)域左移一位杏死，即將此位的數(shù)值與小于區(qū)右邊的值交換泵肄，若大于比較值則不變。如0 3 6 7 5 4淑翼，比較值為4腐巢，小于區(qū)域在0左邊，從0開始區(qū)域右移玄括，到3右移冯丙，到7比比較值大，則不變遭京，到5不變胃惜，到4時(shí)將4與比較區(qū)的右側(cè)值6與4交換泞莉，此時(shí)劃分為0 3 4和6 7 5兩部分。
public class QuickSort(){
public static int[] partition(int[] arr, int left, int right){
int less = left - 1;
int more = right;
while(left < more){
if(arr[left] < arr[right]){
swap(arr, ++less, left++);
}
else if(arr[left] > arr[right]){
swap(arr, --more, left);
}
}
swap(arr, more, right);
// 返回等于區(qū)域邊界的位置
return new int[] {less+1, more};
}
public static void swap(int[] arr, int i, int j) {
int tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}
public static void quickSort(int[] arr, int left, int right){
if(left < right){
// 隨機(jī)選擇一個(gè)數(shù)與最后的數(shù)交換,作為比較值,可使得隨機(jī)快速排序的時(shí)間復(fù)雜度隨機(jī)期望為NlogN
swap(arr, left+(int)(Math.random()*(right-left+1)), right);
// 利用荷蘭國(guó)旗思路船殉，將小的放到左邊鲫趁，大的放到右邊，相等的在中間利虫，并返回相等部分的位置
int[] p = partition(arr, left, right);
// 遞歸思想,p[0]-1為左側(cè)區(qū)域的右邊界
quickSort(arr, left, p[0]-1);
// p[1]+1是右側(cè)區(qū)域的左邊界
quickSort(arr, p[1]+1, right);
}
}
}
3挨厚、堆排序 -- 時(shí)間復(fù)雜度O(N*logN)，空間復(fù)雜度O(1)
思路：二叉樹糠惫，建立大根堆疫剃，然后將最大值排除，堆大小減小寞钥，再?gòu)纳系较抡业酱藭r(shí)堆的最大值慌申，繼續(xù)排序，繼續(xù)減小堆
public class HeapSort(){
public static void heapSort(int[] arr){
if(arr == null || arr.length < 2){
return;
}
for(int i=0; i<arr.length; i++){
heapInsert(arr, i);
}
// 定義堆的大小,以此來(lái)控制需要排序數(shù)值的長(zhǎng)度
int heapSize = arr.length;
// 將第一個(gè)數(shù)與最后一個(gè)數(shù)交換,同時(shí)堆的大小減1
swap(arr, 0, --heapSize);
while(heapSize > 0){
heapify(arr, 0, heapSize);
swap(arr, 0, --heapSize);
}
}
// 構(gòu)建大根堆的過(guò)程,此時(shí)是雖然每顆子樹的最大值為頭節(jié)點(diǎn),但整體是無(wú)序的,知道全局最大值
public static void heapInsert(int[] arr, int index){
// 當(dāng)自節(jié)點(diǎn)的數(shù)值大于其父節(jié)點(diǎn)時(shí),交換位置
while(arr[index] > arr[index-1]/2){
swap(arr, index, (index-1)/2);
// 同時(shí)判斷交換后的節(jié)點(diǎn)的父節(jié)點(diǎn),依次向上
index = (index-1)/2;
}
}
public static void heapify(int[] arr, int index, int heapSize){
// 左孩子
int left = index * 2 + 1;
while(left < heapSize){
// 當(dāng)滿足左下標(biāo)小于size時(shí),返回?cái)?shù)值較大的孩子的下標(biāo)
int largest = left+1<heapSize && arr[left+1]>arr[left] ? left+1 : left;
// 再與父節(jié)點(diǎn)的值比較,返回父節(jié)點(diǎn)及子節(jié)點(diǎn)中最大值的下標(biāo)
largest = arr[largest]>arr[index] ? largest : index;
// 如果當(dāng)前最大值為父節(jié)點(diǎn), 則退出循環(huán)
if(largest == index){
break;
}
// 如果不是則將最大值與父節(jié)點(diǎn)交換, 同時(shí)將父節(jié)點(diǎn)置為最大節(jié)點(diǎn)的索引, 繼續(xù)循環(huán)
swap(arr, largest, index);
index = largest;
// 繼續(xù)得到此時(shí)父節(jié)點(diǎn)的左孩子
left = index * 2 + 1;
}
}
public static void swap(int[] arr, int i, int j) {
int tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}
}
4理郑、冒泡排序 -- 時(shí)間復(fù)雜度O(N^2)蹄溉，空間復(fù)雜度1
思路：從左到右互換逆序的相鄰元素，一輪互換后您炉，最大的值位于最右側(cè)柒爵，遍歷N個(gè)數(shù)，二輪遍歷N-1個(gè)數(shù)...因此復(fù)雜度為N^2
public class BubbleSort(){
public static void bubbleSort(int[] arr){
if(arr == null || arr.length < 2){
return;
}
// 每次從左向右遍歷end個(gè)元素赚爵，互換相鄰元素棉胀，每一輪過(guò)后，最大值將被排在最右側(cè)
for(int end=arr.length-1; end>0; end--){
for(int i=0; i<end; i++){
if(arr[i]>arr[i+1]){
swap(arr, i, i+1);
}
}
}
}
public static void swap(int[] arr, int i, int j){
int tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}
}
5冀膝、插入排序 -- 時(shí)間復(fù)雜度O(N^2)唁奢，空間復(fù)雜度1
思路：針對(duì)某一個(gè)位置i，其前面的數(shù)值均已排好序窝剖，將i插入到前面對(duì)應(yīng)的位置麻掸，類似于抓到撲克牌后，將牌插入的過(guò)程
public class QuickSort(){
public static void insertSort(){
if(arr == null || arr.length < 2){
return;
}
// 從第1個(gè)位置開始, 此時(shí)與第0位置的數(shù)相比
for(int i=1; i<arr.length; i++){
// 每次對(duì)要插入的i位置, 看前面的j-1位置與j位置的大小, 若逆序則互換
for(int j=i-1; j>=0 && arr[j]>arr[j+1]; j--){
swap(arr, j, j + 1);
}
}
}
public static void swap(int[] arr, int i, int j){
int tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}
}
6赐纱、選擇排序 -- 時(shí)間復(fù)雜度O(N^2)脊奋，空間復(fù)雜度1
思路：從數(shù)組中選擇最小元素，將它與數(shù)組的第一個(gè)元素交換位置疙描。再?gòu)臄?shù)組剩下的元素中選擇出最小的元素诚隙，將它與數(shù)組的第二個(gè)元素交換位置
public static void selectionSort(int[] arr){
if (arr == null || arr.length < 2){
return;
}
for(int i=0; i<arr.length; i++){
int minIndex = i;
for(int j=i+1; j<arr.length; j++){
minIndex = arr[j]<arr[minIndex] ? j : minIndex;
}
swap(arr, i, minIndex);
}
}
public static void swap(int[] arr, int i, int j) {
int tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}
7、桶排序
思路：
代碼：
8起胰、排序在系統(tǒng)中的實(shí)現(xiàn)
例如在java中久又，Arrays.sort()是用來(lái)排序的函數(shù)，當(dāng)size小于60時(shí)使用插入排序，在大于60時(shí)籽孙，如果是基本數(shù)據(jù)類型使用快速排序烈评，如果是自己定義的數(shù)據(jù)類型火俄，使用歸并排序犯建；原因是穩(wěn)定性問(wèn)題，快速排序是不穩(wěn)定的瓜客，對(duì)于基本數(shù)據(jù)類型而言适瓦，不是很關(guān)心穩(wěn)定性問(wèn)題，而mergesort是穩(wěn)定的谱仪，對(duì)自己定義的數(shù)據(jù)類型玻熙，排序的穩(wěn)定性就很重要了，關(guān)系到一些邏輯的處理疯攒。
