經典排序算法復習

分類

• 交換類

  • 冒泡
  • 快排

• 分配類

  • 計數排序
  • 基數排序

• 選擇類

  • 選擇排序

  • 堆排序

• 歸并類

  • 歸并排序

• 插入類

  • 直接插入排序

  • 希爾排序

  • 折半插入排序

冒泡排序

基于交換。每一輪找最大值放到數組尾部

//冒泡排序
void bubSort(int* arr,int size){bool sorted=false;while(size--&&!sorted){sorted=true;//檢查某一趟排序是否已完全排好for(int i=0;i<size;i++){// printf("下標為%d的元素和%d的元素正在比較\n",i,i+1);if(arr[i+1]<arr[i]) {swap(&arr[i+1],&arr[i]);sorted=false;}}// printf("第%d趟已比完\n",size);}
}

1. 比較趟數是size-1次,for循環體循環次數為"當前的size"次,即每趟比較次數

2. sorted提高代碼效率,只要排好序就不需再進入下一趟排序

快速排序

冒泡排序優化版本，每趟將數分為大于某基準和小于某基準的兩部分

//快速排序之分區
int partition(int* arr, int low, int high) { //->返回pivot下標int pivot = arr[high];//用low下標值做pivotint i = low, j;for (j=low; j < high; j++) {if (arr[j] < pivot) {swap(&arr[i], &arr[j]);//將小于pivot的元素交換到左側i++;//大于pivot區域的第一個下標加1printf("大于pivot區域的第一個下標值為%d\n", i);}}swap(&arr[i], &pivot);//把pivot歸位return i;
}
void QuickSort(int* arr, int low,int high) {if (low >= high) return;int p=partition(arr, low, high);QuickSort(arr, low, p - 1);QuickSort(arr, p + 1, high);
}

1. i-1為已確定的小于pivot區域的下標值

2. 傳參high=size-1,否則越界

歸并排序

二路歸并，遞歸實現

//歸并排序之兩數組合并
void merge(int* arr, int low, int mid, int high) {//創建臨時數組int* tmp_arr = (int*)malloc(sizeof(int) * (high - low + 1));int i = low, k = low;int j = mid + 1;while (i<=mid&&j<=high)//[low---mid]/ [mid+1---high]兩個數組tmp_arr[k++] = arr[i] < arr[j] ? arr[i++] : arr[j++];while (i <= mid) tmp_arr[k++] = arr[i++];while (j <= high) tmp_arr[k++] = arr[j++];//復制到原數組for (i = low,k=0; i <= high; i++,k++)arr[i] = tmp_arr[k];
}
void MergeSort(int* arr, int low, int high) {if (low >= high) return;int mid = (high + low) / 2;//分MergeSort(arr, low, mid);MergeSort(arr, mid + 1, high);//治merge(arr, low, mid, high);
}

1. 遞歸“分”，再依次“治”；分只需兩個參數low和high，“治”需三個參數，即兩個子數組
2. 遞歸出口：low>=high而不是low>high
3. 每次將此次將排好序的數放到原區間內，每次動態開辟tmp_arr數組空間

堆排序

• 大根堆：父親的權值比左右子樹權值大
• 孩子結點下標編號：2i ,2i+1
  

typedef struct Heap{int* root;int length;
}Heap;
Heap* CreateHeap(int length){Heap* heap=(Heap*)malloc(sizeof(Heap));assert(heap);heap->
}
void pushHeap(Heap* heap,int arr);
int popHeap(Heap* heap);
//偽代碼
for(arr){pushHeap(heap,arr[i]);
}
for(heap){arr[i]=pop(heap)
}
//不定義結構體
void sift(int* array, int low, int high) {int parent = low, child = 2 * parent + 1;//即為左孩子int tmp = array[parent];//當前需要調整的樹的根節點while (child <= high) {//child+1 <= high為防止數組越界if (child+1 <= high && array[child] < array[child + 1]) child = child +1;//存大孩子節點編號if (tmp < array[child]) {array[parent] = array[child];parent = child; child = 2 * parent +1;//繼續向下遍歷}else break;}array[parent] = tmp;
}
void HeapSort(int* array, int size) {int i;//非葉子結點的最大編號for (i = (size-1-1) / 2; i >= 0; i--) {sift(array, i, size-1);}//建大根堆for (i = size-1; i >= 1; i--) {//循環n-1次完成堆排序swap(&array[0],&array[i]);// int tmp = array[0];// array[0] = array[i];// array[i] = tmp;sift(array, 1, i - 1);}
}

1. sift參數為low,high,high可以取到且為size-1
2. 大根堆建立的基礎是孩子也為大根堆,所以從后往前依次建堆
3. 最大數移到數組最后則表示其出堆,high-1

插入排序

把無序區的元素插入到有序區對應的位置

//直接插入排序(從小到大排)
void insert_sort(int* array, int size) {int j,tmp;for (int i = 1; i < size; i++) {//n趟tmp = array[i];int end = i-1;for (; end >= 0; end--) {//每趟比較次數因數據有序程度而變化，最壞是i次，則移動次數最壞是i+2次if (tmp < array[end]) array[end + 1] = array[end];else break;//如果大于等于,跳出循環!!!!end不能再--}printf("下標%d元素找到插入位置了:%d\n",i,end+1);printArray(array,size);array[end+1] = tmp;}
}

1. 找end位置,找到就跳出循環!! else break;如果不加end每次循環到1
2. end+1<size 防止數組越界
3. end+1為第i個節點的插入位置