八大排序總結
- 目錄:
- 一.插入排序 (InsertSort)
- 二.希爾排序 (ShellSort)
- 三.選擇排序 (SelectSort)
- 四.堆排序 (HeapSort)
- 五.冒泡排序 (BubbleSort)
- 六.快速排序 (QuickSort)
- 1.hoare法
- 2.挖坑法
- 3.前后指標法
- 七.歸并排序 (MergeSort)
- 1.遞回實作
- 2.非遞回實作
- 八.計數排序 (CountSort)
目錄:
一.插入排序 (InsertSort)
對于插入排序的本質就是從后向前將所有的元素找到對應的位置進行插入即可.
void insertSort(int* arr, int n){
//假設第一個資料是有序的
//未插入資料[1,n)
for (int i = 0; i < n; ++i){
//從有序的最后一個位置進行遍歷
int end = i - 1;
int data = arr[i];
while (end >= 0 && arr[end] >= data){ //滿足條件時
//較大的資料向后移動
arr[end + 1] = arr[end]; //資料后移
--end; //回圈
}
arr[end + 1] = data; //直接插入
}
}
二.希爾排序 (ShellSort)
void shellSort(int* arr, int n){
int gap = n; //創建gap值
//一趟哈希排序
while (gap > 1){
gap = gap / 3 + 1; //讓其等于一個值進行交換
for (int i = gap; i < n; ++i){ //回圈內部
//同組資料,最后一個有序陣列的位置
int end = i - gap;
//待插入的資料
int data = arr[i];
while (end >= 0 && arr[end]>data){
arr[end + gap] = arr[end];
end -= gap; //gap逐漸減到1
}
arr[end + gap] = data; //交換
}
}
}
三.選擇排序 (SelectSort)
選擇排序從前向后遍歷,找后面小于這個數(最小),然后將兩者進行交換,依次向后移一位.
void selectSort(int* arr, int n){
int start = 0;
int end = n - 1; //定義尾部節點
while (start < end){ //回圈開始
//首先找到最小值的位置
int minIdx = start;
int i;
for (i = start + 1; i <= end; ++i){ //進行遍歷
if (arr[i] < arr[minIdx]) //如果存在最小的
minIdx=i; //讓它等于i
}
//將最小值存在起始位置
Swap(arr, start, minIdx); //這里呼叫了一個最最最簡單的交換元素,我就不具體寫了,相信大家也會.
//回圈
++start;
}
}
四.堆排序 (HeapSort)
void shiftDown(int* arr, int n, int parent){
int child = 2 * parent + 1; //最后一個孩子節點的位置
while (child < n){ //回圈
if (child + 1 < n&&arr[child + 1] > arr[child]) //存在則繼續
++child;
if (arr[child]>arr[parent]){ //孩子節點大于父節點,則交換
Swap(arr, child, parent); //交換,如同圖中的橙色線
parent = child; //更新
child = 2 * parent + 1; //更新孩子節點
}
else
break; //不滿足直接結束
}
}
void heapSort(int* arr, int n){
for (int i = (n - 2) / 2; i >= 0; --i){
shiftDown(arr, n, i); //進行回圈呼叫
}
int end = n - 1; //最后的節點依次減1
while (end > 0){ //end>0繼續回圈
Swap(arr, end, 0); //交換函式
shiftDown(arr, end, 0); //交換最后一個
--end; //直到end=0,回圈結束
}
}
五.冒泡排序 (BubbleSort)
void bubbleSort(int* arr,int n){
//相鄰元素進行比較
//遍歷范圍:0-為排序的最后一位
int end = n;
while (end > 1){
//第一次冒泡排序
for (int i = 1; i < end; ++i){
if (arr[i - 1]>arr[i]){ //這里的i和i-1就相當于i和j
//大的元素向后移動
Swap(arr, i - 1, i); //簡單交換函式,不描寫介面
}
}
--end; //主要進行回圈
}
}
六.快速排序 (QuickSort)
1.hoare法
//獲取基準值
//下面輸出的都會基準值
//這段代碼主要是理解,其結構不難,不進行過多的注釋
int getMid(int* arr, int begin, int end){
int mid = begin + (end - begin) / 2;
if (arr[begin] > arr[mid]){ //==========1.開始大于中間
if (arr[mid] > arr[end])
return mid;
else if (arr[begin] > arr[end])
return end;
else
return begin;
}
else{ //=========2.開始小于等于中間
if (arr[mid] < arr[end])
return mid;
else if (arr[begin] < arr[end])
return end;
else
return begin;
}
}
//劃分函式 實作陣列的劃分,進行分別遍歷的操作
int partion(int* arr, int begin, int end){
//獲取基準值位置
int mid = getMid(arr, begin, end);
//把基準值放到起始位置
Swap(arr, begin, end);
//首先選擇基準值
int key = arr[begin];
int start = begin;
while (begin < end){ //后置比較大的時候
//1.==============================從后向前找小于基準值的位置
while (begin < end&&arr[end] >= key)
--end;
//2.===============================從前向后找大于的位置
while (begin < end&&arr[begin] <= key)
++begin;
//3.===============================用函式交換
Swap(arr, begin, end);
}
//交換基準值與相遇位置的資料
Swap(arr, start, begin);
return begin;
}
//快速排序
void quickSort(int* arr, int begin, int end){
if (begin >= end)
return;
//div:一次劃分后基準值
int div = partion(arr, begin, end);
//分別進行左右兩邊的快排
//[begin,div-1]
//[div+1,end]
quickSort(arr, begin, div - 1);
quickSort(arr, div + 1, end);
}
2.挖坑法
//獲取中間值的函式介面
int getMid(int* arr, int begin, int end){
int mid = begin + (end - begin) / 2; //獲取中間值
if (arr[begin] > arr[mid]){ //對所處的位置進行比較,最侄訓取中間的值
//很簡單的,我就不具體解釋了,大家多看看就行了
if (arr[mid] > arr[end])
return mid;
else if (arr[begin] > arr[end])
return end;
else
return begin;
}
else{
if (arr[mid] < arr[end])
return mid;
else if (arr[begin] < arr[end])
return end;
else
return begin;
}
}
int partion2(int* arr, int begin, int end){
int mid = getMid(arr, begin, end);
Swap(arr, begin, mid);
//第一個基準值,也就是初始為坑的位置
int key = arr[begin];
while (begin < end){
//從后往前找到小的
while (begin < end&&arr[end] >= key)
--end;
//進行填坑
arr[begin] = arr[end];
//從前往后找大的
while (begin < end&&arr[begin] <= key)
++begin;
//填坑
arr[end] = arr[begin];
}
arr[begin] = key;
return begin;
}
//主要的對于下面寫的劃分方式的呼叫
void quickSort(int* arr, int begin, int end){
if (begin >= end) //如果開始的 大于結束的則為越界,直接結束
return;
//div:一次劃分后基準值
//int div = partion(arr, begin, end);
//int div = partion2(arr, begin, end);
int div = partion3(arr, begin, end); //對下面兩個種方法進行呼叫
//分別進行左右兩邊的快排
//[begin,div-1]
//[div+1,end]
quickSort(arr, begin, div - 1); //對上面劃分的左右兩個區間進行回圈呼叫
quickSort(arr, div + 1, end);
}
3.前后指標法
//獲取中間值的函式介面
int getMid(int* arr, int begin, int end){
int mid = begin + (end - begin) / 2; //獲取中間值
if (arr[begin] > arr[mid]){ //對所處的位置進行比較,最侄訓取中間的值
//很簡單的,我就不具體解釋了,大家多看看就行了
if (arr[mid] > arr[end])
return mid;
else if (arr[begin] > arr[end])
return end;
else
return begin;
}
else{
if (arr[mid] < arr[end])
return mid;
else if (arr[begin] < arr[end])
return end;
else
return begin;
}
}
int partion3(int* arr, int begin, int end){
int mid = getMid(arr, begin, end);
Swap(arr, begin, mid);
//上一個小于基準值的位置
int prev = begin;
//下一個小于基準值的位置
int cur = begin + 1;
int key = arr[begin];
while (cur <= end){
//當cur走到下一個基準值的位置的時候,判斷是否連續
if (arr[cur]<key && ++prev != cur) {
//不連續,交換資料
Swap(arr, prev,cur);
}
++cur; //cur繼續向下走,prev不動
}
Swap(arr, begin, prev); //與基準值進行交換,且固定
return prev;
}
//主要的對于下面寫的劃分方式的呼叫
void quickSort(int* arr, int begin, int end){
if (begin >= end) //如果開始的 大于結束的則為越界,直接結束
return;
//div:一次劃分后基準值
//int div = partion(arr, begin, end);
//int div = partion2(arr, begin, end);
int div = partion3(arr, begin, end); //對下面兩個種方法進行呼叫
//分別進行左右兩邊的快排
//[begin,div-1]
//[div+1,end]
quickSort(arr, begin, div - 1); //對上面劃分的左右兩個區間進行回圈呼叫
quickSort(arr, div + 1, end);
}
七.歸并排序 (MergeSort)
1.遞回實作
//歸并排序
void merge(int* arr, int begin, int mid, int end, int* tmp){
//遞增
int begin1 = begin; //前半個區間
int end1 = mid;
int begin2 = mid + 1; //后半個區間
int end2 = end;
//輔助空間
int idx = begin;
//合并有序的序列
//檢查是否越界
while (begin1 <= end1&&begin2 <= end2){ //如果沒有越界
if (arr[begin1] <= arr[begin2]) //如果第一個元素小
tmp[idx++] = arr[begin1++]; //先將第一個輸入
else
tmp[idx++] = arr[begin2++]; //否則,先將第二個輸入
}
//上面的回圈進行,直到結束
//判斷是否有沒有合并的元素
if (begin1 <= end1) //如果1中有剩余
//直接將1中剩余的元素拷貝到序列中
memcpy(tmp + idx, arr + begin1, sizeof(int)*(end1 - begin1 + 1));
if (begin2 <= end2)
//如果2中有剩余,直接將2中的拷貝過去
memcpy(tmp + idx, arr + begin2, sizeof(int)*(end2 - begin2 + 1));
//合并后的序列拷貝到原始的資料
memcpy(arr + begin, tmp + begin, sizeof(int)*(end - begin + 1));
}
//======================遞回
void _mergeSort(int* arr, int begin, int end, int* tmp){
if (begin >= end) //判空
return;
int mid = begin + (end - begin) / 2; //找到中間元素
//先進行子序列的合并
_mergeSort(arr, begin, mid, tmp);
_mergeSort(arr, mid + 1, end, tmp);
//上面兩部是對于子序列的合并,也就是將一個個的小點點進行合并
//合并兩個有序的子序列
merge(arr, begin, mid, end, tmp);
}
void mergeSort(int* arr, int n){
//申請輔助空間
int* tmp = (int*)malloc(sizeof(int)*n); //申請空間方便存放
_mergeSort(arr, 0, n - 1, tmp); //呼叫函式
free(tmp); //將申請用完的空間進行釋放
}
2.非遞回實作
//歸并排序
void merge(int* arr, int begin, int mid, int end, int* tmp){
//遞增
int begin1 = begin; //前半個區間
int end1 = mid;
int begin2 = mid + 1; //后半個區間
int end2 = end;
//輔助空間
int idx = begin;
//合并有序的序列
//檢查是否越界
while (begin1 <= end1&&begin2 <= end2){ //如果沒有越界
if (arr[begin1] <= arr[begin2]) //如果第一個元素小
tmp[idx++] = arr[begin1++]; //先將第一個輸入
else
tmp[idx++] = arr[begin2++]; //否則,先將第二個輸入
}
//上面的回圈進行,直到結束
//判斷是否有沒有合并的元素
if (begin1 <= end1) //如果1中有剩余
//直接將1中剩余的元素拷貝到序列中
memcpy(tmp + idx, arr + begin1, sizeof(int)*(end1 - begin1 + 1));
if (begin2 <= end2)
//如果2中有剩余,直接將2中的拷貝過去
memcpy(tmp + idx, arr + begin2, sizeof(int)*(end2 - begin2 + 1));
//合并后的序列拷貝到原始的資料
memcpy(arr + begin, tmp + begin, sizeof(int)*(end - begin + 1));
}
//=========================非遞回
void mergeSortNoR(int* arr, int n){
int* tmp = (int*)malloc(sizeof(int)*n); //動態記憶體申請
//子序列的步長
int step = 1; //步長也就是內部有一個元素步長為1,兩個則為2
while (step < n){ //步長最大就是原來的序列
for (int idx = 0; idx < n; idx += 2 * step){ //注意這里,步長每次增加2!!!!!!!!
//找到兩個待合并的子序列區間
//[begin,mid] [mid+1,end]
int begin = idx;
int mid = idx + step - 1;
//判斷是否存在第二個子序列
if (mid >= n - 1)
continue; //不存在第二個子序列,直接跳過
int end = idx + 2 * step - 1;
//判斷第二個子序列是否越界
if (end > n)
end = n - 1;
merge(arr, begin, mid, end, tmp);
}
//更新步長
step *= 2;
}
}
八.計數排序 (CountSort)
//====================================3.非比較排序(計數排序)
//所消耗的空間過大 空間復雜度大
void countSort(int* arr, int n){
//找到最大和最小值
int max, min;
min = max = arr[0];
for (int i = 1; i < n; ++i){ //這里是進行回圈選出最大值和最小值
if (arr[i]>max)
max = arr[i];
if (arr[i ]< min)
min = arr[i];
}
//計算出范圍
int range = max - min + 1;
//創建一個計數陣列,初始化為0
int* countArr = (int*)calloc(range, sizeof(int)); //動態開辟一個全0的陣列
//計數
for (int i = 0; i < n; ++i){
countArr[arr[i] - min]++; //對其進行計數
}
//遍歷計數陣列
int idx = 0;
for (int i = 0; i < range; ++i){ //遍歷整個范圍
while (countArr[i]--){ //依次減減
arr[idx++] = i + min; //對其進行回圈賦值
}
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/290879.html
標籤：其他
上一篇：Linux云計算 --中國三大電商大廠都在使用的《 GitLab與Jenkins結合構建持續集成(CI)環境》是如何排列