排序的簡單分類
排序的分類：排序分為插入排序、選擇排序、交換排序、歸并排序四大類；
我們將待排序的陣列設為a【】，元素個數位n
插入排序
1.直接插入
直接插入排序是一種最簡單的排序方法，它的基本操作是將一個記錄插入到已經排好序的有序表中，從而得到一個新的記錄增加1的有序表，
*
代碼附上
void InsertSort(int* a, int n)
{
// [0, end]有序 end+1位置的值插入[0, end]，讓[0, end+1]有序
for (int i = 0; i < n-1; ++i)
{
int end = i;
int tmp = a[end + 1];
while (end >= 0)
{
if (a[end] > tmp)
{
a[end + 1] = a[end];
--end;
}
else
{
break;
}
}
a[end + 1] = tmp;
}
}
2.希爾插入排序
按一定跨度d兩兩進行比對并按序交換位置，進行完一輪比對后跨度縮小再進行下一輪，經過幾輪后先將整個序列變成部分有序，然后再進行直接插入排序，減少直接插入排序的開銷，:希爾排序是把記錄按下標的一定增量分組(n/2=a,增量為a)，對每組使用直接插入排序演算法排序；隨著增量逐漸減少，每組包含的關鍵詞越來越多，當增量減至1時，整個檔案恰被分成一組，演算法便終止.
是對插入排序的一個改進,是非穩定排序演算法
圖示如下
void ShellSort(int* a, int n)
{
int gap = n;
while (gap > 1)
{
//gap = gap / 2; // logN
gap = gap / 3 + 1; // log3N 以3為底數的對數
// gap > 1時都是預排序 接近有序
// gap == 1時就是直接插入排序 有序
// gap很大時，下面預排序時間復雜度O(N)
// gap很小時，陣列已經很接近有序了，這時差不多也是(N)
// 把間隔為gap的多組資料同時排
for (int i = 0; i < n - gap; ++i)
{
int end = i;
int tmp = a[end + gap];
while (end >= 0)
{
if (a[end] > tmp)
{
a[end + gap] = a[end];
end -= gap;
}
else
{
break;
}
}
a[end + gap] = tmp;
}
}
}
選擇排序
1.簡單選擇排序
簡單選擇排序是取出一個元素依次以后面的元素比較，如果后面的元素比前面的元素小，就進行交換、
2.堆排序
利用資料結構中的二叉樹建立大根堆和小根堆，再用堆頂和尾部交換，利用遞回的思想排序
對于堆排序我們應該知道的知識
1.1 大根堆和小根堆
性質：每個結點的值都大于其左孩子和右孩子結點的值，稱之為大根堆；每個結點的值都小于其左孩子和右孩子結點的值，稱之為小根堆
還有一個基本概念：查找陣列中某個數的父結點和左右孩子結點，比如已知索引為i的數，那么
1.父結點索引：(i-1)/2（這里計算機中的除以2，省略掉小數）
2.左孩子索引：2*i+1
3.右孩子索引：2*i+2
**先建堆
void AdjustDwon(int* a, int n, int root)
{
int parent = root;
int child = parent * 2 + 1; // 默認是左孩子
while (child < n)
{
// 1、選出左右孩子中大的那一個
if (child + 1 < n && a[child+1] > a[child])
{
child += 1;
}
if (a[child] > a[parent])
{
Swap(&a[child], &a[parent]);
parent = child;
child = parent * 2 + 1;
}
else
{
break;
}
}
}
再選數
void HeapSort(int* a, int n)
{
// 建堆 時間復雜度：O(N)
for (int i = (n - 1 - 1) / 2; i >= 0; --i)
{
AdjustDwon(a, n, i);
}
// 排升序，建大堆還是小堆？建大堆
int end = n - 1;
while (end > 0)
{
Swap(&a[0], &a[end]);
AdjustDwon(a, end, 0);
--end;
}
}
交換排序
1.冒泡排序
利用逐個交換，使大的元素排到上面，再使最大的不動，依次將元素浮在上面，就是所謂的冒泡排序，
void BubbleSort(int* a, int n)
{
for (int j = 0; j < n; ++j)
{
int exchange = 0;
for (int i = 1; i < n - j; ++i)
{
if (a[i - 1] > a[i])
{
Swap(&a[i - 1], &a[i]);
exchange = 1;
}
}
if (exchange == 0)
{
break;
}
}
//另一種寫法
//int end = n;
//while (end > 0)
//{
// for (int i = 1; i < end; ++i)
// {
// if (a[i - 1] > a[i])
// {
// Swap(&a[i - 1], &a[i]);
// }
// }
// --end;
//}
}
2.快速排序
快速排序在每一輪挑選一個基準元素，并讓其他比它大的元素移動到數列一邊，比它小的元素移動到數列的另一邊，從而把數列拆解成了兩個部分，
我們先對快速排序進行初步分析
a.挖坑法
對于快速排序，我們先取左邊第一個值作為標準值，把它放在陣列的中間位置，并且這個數字的左邊是小于的，右邊是大于的，然后我們利用遞回的思想對左右邊區間進行同樣的操作，最終可以得到有序陣列
代碼附上
void QuickSort(int* a, int left,int right)
{
if (left >= right)
return;
//遞回結束的條件
/*int Index = MidIndex(a, left, right);
Swap(&a[Index],&a[left]);*/
int begin = left, end = right ;
int key =a[begin];
int Pivot = begin;
while (begin < end)
{
while (begin<end && a[end] >= key)//右邊找小，放左邊
{
--end;
}
a[Pivot] = a[end];
Pivot = end;
while (begin<end && a[begin] <= key)//左邊找大，放右邊
{
++begin;
}
a[Pivot] = a[begin];
Pivot = begin;
}
Pivot = begin;
a[Pivot] = key;
QuickSort(a, left, Pivot - 1);//進行遞回
QuickSort(a, Pivot + 1, right);
}
但是當陣列是有序的時候，該排序就會變得不便捷，因為在每次排序中我都要進行n，n-1，n-2————，這樣就很難體現快速排序的優越性
這里我們采用三數取中，使標準值不是陣列的最大或者最小值，這樣可以避免有序陣列排序時的尷尬情況
代碼如下
void QuickSort(int* a, int left,int right)
{
if (left >= right)
return;
int Index = MidIndex(a, left, right);
Swap(&a[Index],&a[left]);
int begin = left, end = right ;
int key =a[begin];
int Pivot = begin;
while (begin < end)
{
while (begin<end && a[end] >= key)//右邊找小，放在左邊
{
--end;
}
a[Pivot] = a[end];
Pivot = end;
while (begin<end && a[begin] <= key)//左邊找大，放在右邊
{
++begin;
}
a[Pivot] = a[begin];
Pivot = begin;
}
Pivot = begin;
a[Pivot] = key;
QuickSort(a, left, Pivot - 1);
QuickSort(a, Pivot + 1, right);
}
遞回演示圖如下
對于挖坑法，每次把左邊元素放進中間為O（n），遞回為logn，時間復雜度為n*logn
b.小區間優化
在快速排序挖坑法上，往往資料量很大的時候，在最后幾次遞回會產生很大的時間復雜度，在這種情況下挖坑法就不再優越，我們就對挖坑法進行的優化，最后幾次遞回我們采用插入排序的方法，
代碼附上
void QuickSort(int* a, int left, int right)
{
if (left >= right)
return;
int keyIndex = PartSort3(a, left, right);
// [left, right]
// [left, keyIndex-1] keyIndex [keyIndex+1, right]
// 左子區間和右子區間有序，我們就有序了，如果讓他們有序呢？ 分治遞回
// QuickSort(a, left, keyIndex - 1);
// QuickSort(a, keyIndex + 1, right);
// 小區間
if (keyIndex - 1 - left > 10)
{
QuickSort(a, left, keyIndex - 1);
}
else
{
InsertSort(a + left, keyIndex - 1 - left + 1);
}
if (right - (keyIndex + 1) > 10)
{
QuickSort(a, keyIndex + 1, right);
}
else
{
InsertSort(a + keyIndex + 1, right - (keyIndex + 1) + 1);
}
}*
挖坑法的變形—左右指標法
圖示如下
代碼附上
```c
int PartSort2(int* a, int left, int right)
{
int index = GetMidIndex(a, left, right);
Swap(&a[left], &a[index]);
int begin = left, end = right;
int keyi = begin;
while (begin < end)
{
// 找小
while (begin < end && a[end] >= a[keyi])
{
--end;
}
// 找大
while (begin < end && a[begin] <= a[keyi])
{
++begin;
}
Swap(&a[begin], &a[end]);
}
Swap(&a[begin], &a[keyi]);
return begin;
}
# 歸并排序
歸并排序（MERGE-SORT）是建立在歸并操作上的一種有效的排序演算法,該演算法是采用分治法（Divide and Conquer）的一個非常典型的應用，將已有序的子序列合并，得到完全有序的序列；即先使每個子序列有序，再使子序列段間有序，若將兩個有序表合并成一個有序表，稱為二路歸并，
```c
void _MergeSort(int* a, int left, int right, int* tmp)
{
if (left >= right)
return;//遞回結束條件
int Mid = (left + right) >> 1;//取中間值
//兩邊區間都有序了，陣列就有序了
_MergeSort(a, left, Mid, tmp);
_MergeSort(a, Mid + 1, right, tmp);
//接下來就是排序的程序；
//先定下標
int begin1 = left; int end1 = Mid;
int begin2 = Mid + 1; int end2 = right;
int index = left;//新建臨時陣列的下標
while (begin1 <= end1 && begin2 <= end2)//回圈繼續的條件
{
if (a[begin1] < a[begin2])
{
tmp[index++] = tmp[begin1++];
}
else
{
tmp[index++] = tmp[begin2++];
}
}
while (begin1<= end1)
{
tmp[index++] = tmp[begin1++];
}
while (begin2 <= end2)
{
tmp[index++ ] = tmp[begin2++];
}
//將臨時陣列的元素拷貝回去
for (int i = left; i <= left; i++)
{
a[i] = tmp[i];
}
}
void MergeSort(int* a, int n)
{
int* tmp = (int*)malloc(sizeof(int) * n);
_MergeSort(a, 0, n - 1, tmp);
free(tmp);
}
對于歸并排序的遞回可以下圖粗略表示
結束語
排序是資料結構中重要的知識，
創造不易，請各位看官們三連加關注吧！
轉載請註明出處，本文鏈接：https://www.uj5u.com/ruanti/286644.html
標籤：其他
上一篇：C語言中運算子介紹
下一篇：指標的一些筆試題