C++九種排序具體實現代碼
更新時間：2020年04月09日 10:21:47 作者：DX3906
這篇文章主要介紹了C++九種排序具體實現代碼，文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值，需要的朋友們下面隨著小編來一起學習學習吧
本文內容會根據博主所需進行更新，希望大家多多關照。
直接插入排序
void InsertSort(int r[])
{
int n = sizeof(r) / sizeof(r[0]);
for(int i = 1; i < n; ++i)
{
for(int j = i - 1; j >= 0; --j)
{
if(r[j+1] < r[j])
{
int s = r[j+1];
r[j+1] = r[j];
r[j] = s;
}
}
}
}
折半插入排序
void BinInsertSort(int r[])
{
int n = sizeof(r) / sizeof(r[0]);
for(int i = 1; i < n; ++i)
{
int s = r[i];
int low = 0;
int high = i - 1;
while(low <= high)
{
int mid = (low + high) / 2; //mid位置為要找的數
if(s < r[mid])
high = mid - 1;
else
low = mid + 1;
}
for(int j = i - 1; j >= high + 1; --j) //high+1即mid，執(zhí)行數的后移，直到mid的數后移
r[j+1] = r[j];
r[high+1] = s; //mid位置就存放本身
}
}
希爾排序
void ShellSort(int r[])
{
int n = sizeof(r) / sizeof(r[0]);
int step = n / 2;
while(step >= 1)
{
for(int i = step; i < n; ++i)
{
for(int j = i - step; j >= 0; j -= step)
{
if(r[j+step] < r[j])
{
int s = r[j+step];
r[j+step] = r[j];
r[j] = s;
}
}
}
step /= 2;
}
}
直接選擇排序
void SelectSort(int r[])
{
int n = sizeof(r) / sizeof(r[0]);
for(int i = 0; i < n - 1; ++i)
{
int samll = i;
for(int j = i + 1; j < n; ++j)
{
if(r[small] > r[j])
samll = j;
}
if(small != i)
{
int s = r[i];
r[i] = r[small];
r[small] = s;
}
}
}
堆排序
void HeapAdjust(int r[]; int i; int j) //調整堆
{
int child = 2 * i;
int s = r[i]; //s臨時存放結點數據
while(child <= j)
{
if(child < j && r[child+1] > r[child]) //比較2個子樹
++child;
if(s >= r[child]) //結點與大子樹比較
break;
r[child/2] = r[child]; //如果大子樹比結點大，互換
child = 2 * child; //繼續(xù)向子樹檢索
}
r[child/2] = s; //結點的數為最大的數
}
void HeapSort(int r[]) //建堆
{
int n = sizeof(r) / sizeof(r[0]);
for(int i = n / 2 - 1; i >= 0; --i) //只有n/2-1前的下標才有子樹
{
HeapAdjust(r, i, n - 1); //構造大頂堆，結點都比子樹大，最后根節(jié)點為最大的數
}
for(int i = n - 1; i > 0; --i)
{
//將當前堆頂元素與當前堆尾元素互換，即將最大的數移到末尾
int s = r[0];
r[0] = r[i];
r[i] = s;
HeapAdjust(r, 0, i -1); //將剩下的元素繼續(xù)調整，最后變成由小到大的順序
}
}
冒泡排序
void BubbleSort(int r[])
{
int n = sizeof(r) / sizeof(r[0]);
for(int i = 0; i < n - 1; ++i)
{
for(int j = 0; j < n - 1 - i; ++j)
{
if(r[j] > r[j+1])
{
int s = r[j];
r[j] = r[j+1];
r[j+1] = s;
}
}
}
}
快速排序
int Partition(int r[], int low, int high)
{
int pivotkey = r[low];
int i = low;
int j = high;
while(i < j)
{
while(i < j && r[j] > pivotkey) //從j往前找，找出第一個比pivotkey小的數
--j;
if(i < j)
{
r[i] = r[j];
++i;
}
while(i < j && r[i] < pivotkey) //從i往后找，找出第一個比pivotkey大的數
++i;
if(i < j)
{
r[j] = r[i];
--j;
}
}
r[j] = pivotkey; //完成最終交換
return j; //返回分界點，前面的數都比pivotkey小，后面的數都比pivokey大
}
void QuickSort(int r[], int low, int high) // 傳數組、0和長度-1
{
if(low < high)
{
int pivot = Partition(r, low, high);
QuickSort(r, low, pivot - 1); //遞歸，前半部分繼續(xù)進行快速排序
QuickSort(r, pivot + 1; high); //遞歸，后半部分繼續(xù)進行快速排序
}
}
歸并排序
void copyArray(int source[], int dest[], int len, int first)
{
int i;
int j = first;
for(i = 0; i < len; ++i)
{
dest[j] = source[i];
++j;
}
}
void merge(int a[], int left, int right)
{
int begin1 = left;
int mid = (left + right) / 2;
int begin2 = mid + 1;
int newArrayLen = right - left + 1;
int *b = (int*)malloc(newArrayLen * sizeof(int));
int k = 0;
while(begin1 <= mid && begin2 <= right) //找出2組中比較后小的那個數按順序放進b空間
{
if(a[begin1] <= a[begin2])
b[k++] = a[begin1++];
else
b[k++] = a[begin2++];
}
//把剩下的數放進b空間
while(begin1 <= mid)
b[k++] = a[begin1++];
while(begin2 <= right)
b[k++] = a[begin2++];
copyArray(b, a, newArrayLen, left); //把b空間的數寫回原數組
free(b);
}
void MergeSort(int r[], int left, int right) //傳數組、0和長度-1
{
int i;
//至少有兩個元素才進行排序
if(left < right)
{
i = (left + right) / 2;
MergeSort(r, left, i); //前半部分遞歸
MergeSort(r, i + 1, right); //后半部分遞歸
merge(r, left, right); //10個數的比較順序為[0,1][0,2][3,4][0,4][5,6][5,7][8,9][5,9][0,9]
}
}
桶排序
void insert(list<int> &bucket, int val)
{
auto iter = bucket.begin();
while(iter != bucket.end() && val >= *iter)
++iter;
//insert會在iter之前插入數據，這樣可以穩(wěn)定排序
bucket.insert(iter, val);
}
void BuckdeSort(vector<int> &arr)
{
int len = arr.size();
if(len <= 1)
return;
int min = arr[0], max = min;
for(int i = 1; i < len; ++i) //找出最小值和最大值
{
if(min > arr[i])
min = arr[i];
if(max < arr[i])
max = arr[i];
}
int k = 10; //桶的大小
//向上取整，例如[0,9]有10個數，就有(9-0)/k+1=1個桶
int bucketsNum = (max - min) / k + 1; //桶的個數
vector<list<int>> buckets(bucketsNum);
for(int i = 0; i < len; ++i)
{
int value = arr[i];
//(value-min)/k就是在哪個桶里面
insert(buckets[(value-min)/k], value); //將數據放到各個桶里并排序
}
int index = 0;
for(int i = 0; i < bucketsNum; ++i)
{
if(buckets[i].size())
{
for(auto &value : buckets[i])
arr[index++] = value;
}
}
}
到此這篇關于C++九種排序具體實現代碼的文章就介紹到這了,更多相關C++ 排序內容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關文章希望大家以后多多支持腳本之家！
相關文章
以下是對C++中的函數指針與函數對象的使用進行了詳細的分析介紹，需要的朋友可以參考下2013-07-07
這篇文章主要介紹了C語言中的初階函數，介紹了其相關概念，具有一定參考價值。需要的朋友可以了解下，希望能夠給你帶來幫助2021-11-11
在本篇文章里小編給大家整理的是關C語言數據存儲，小編覺得這篇文章寫的很不錯，有需要的朋友們可以學習參考下，希望能夠給你帶來幫助2021-10-10
這篇文章主要為大家詳細介紹了C語言實現消消樂小游戲，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2020-12-12
這篇文章主要介紹了C語言執(zhí)行程序時遇到的常見問題及解決方案，具有很好的參考價值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教2023-03-03
這篇文章主要介紹了C語言對磁盤文件進行快速排序簡單實例的相關資料,需要的朋友可以參考下2017-06-06
這篇文章主要給大家介紹了關于C語言不使用strcpy函數如何實現字符串復制功能的相關資料，文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值，需要的朋友們下面隨著小編來一起學習學習吧2021-02-02
這篇文章主要介紹了C++ 數據結構鏈表的實現代碼的相關資料,需要的朋友可以參考下2017-01-01
Visual Studio Code 從簡介、安裝到配置所需插件詳細介紹
這篇文章給大家介紹到vs與vs code的區(qū)別，并且會詳細介紹vscode的安裝步驟，和我所了解過的插件配置，感興趣的朋友跟隨小編一起看看吧2020-03-03
這篇文章主要為大家詳細介紹了C語言實現猜數字的小游戲，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2021-01-01