#pragma once
#include
#include
using namespace std;
//直接排序：指的是設(shè)定2個(gè)下標(biāo)/指針。然后從下標(biāo)1開(kāi)始進(jìn)行比較，
//升序情況下：若在前的下標(biāo)/指針大于當(dāng)前比較數(shù)值。就進(jìn)行數(shù)組的后移。
//直到滿足當(dāng)前序列值。然后最終將當(dāng)前比較數(shù)值進(jìn)行替換。
//PS：總有一個(gè)指針遍歷比較數(shù)組（k，arry[i]）
//時(shí)間復(fù)雜度為：0（n^2）,空間復(fù)雜度0（1）
void InsertSort(int* arry,int len)
{
assert(arry);
for(int i = 1; i < len;++i)
{
int j = i-1;
int k = arry[i];
while(j > -1 && arry[j] > k)
{
arry[j + 1] = arry[j];
--j;
}
arry[j+1] = k;
}
}
//希爾排序：在直接排序的基礎(chǔ)上增加分組Gap值，
//利用Gap值，比較對(duì)應(yīng)（len/gap）* i的位置。每個(gè)位置代表一個(gè)分組
//然后將i的值依次增加到len-gap的位置相當(dāng)于我已經(jīng)比較了每個(gè)對(duì)應(yīng)分組，使當(dāng)前序列趨近于有序。
//然后我們縮小gap值的范圍，使其接近于2，證明還需要進(jìn)行分組排序。
//0(n^2),0(1);
void ShellSort(int *arry,int len)
{
assert(arry);
int gap = len;
while(gap > 1)
{
gap = gap/3 + 1;
for(int i = 0; i < len - gap;++i)
{
int j = i;
int k = arry[i+gap];
while(j > -1 && arry[j] > k)
{
arry[j + gap] = arry[j];
j -= gap;
}
arry[j+gap] = k;
}
}
}
//選擇排序：其實(shí)這個(gè)排序的思路比較簡(jiǎn)單，我們只需要每次遍歷數(shù)組
//得到最小/最大（或者2者都選），然后將最大值最小值分別丟到數(shù)組的最左端還有最右端然后縮小范圍就可以了。
//然后值得注意的是。我們?cè)谕瑫r(shí)得出當(dāng)前最大最小值時(shí)候，需要注意
//當(dāng)前選出的最大值最小值在進(jìn)行其中一次交換后，會(huì)不會(huì)將max與min相交換。
//0（n^2）,0(1)
void SelectSort(int *arry, int len)
{
assert(arry);
for(int i = 0, j = len-1;i < j;++i,--j)
{
int min = i;
int max = j;
for(int k = i;k <= j;++k)
{
if(arry[k] < arry[min])
{
min = k;
}
if(arry[k] > arry[max])
{
max = k;
}
if(min != i)
{
int temp = arry[min];
arry[min] = arry[i];
arry[i] = temp;
if(max == i)
max = min;
}
if(max!= j)
{
int temp = arry[max];
arry[max] = arry[j];
arry[j] = temp;
}
}
}
}
//冒泡排序：冒泡排序比較簡(jiǎn)單，就不多說(shuō)了。
//需要注意的是我們可以利用一個(gè)標(biāo)記值來(lái)確定我們需不需要進(jìn)行這一次的冒泡
//如果需要進(jìn)行冒泡的話我們的標(biāo)記值就會(huì)設(shè)置位開(kāi)關(guān)。
//然后我們就可以減少我們所需要排序的次數(shù)。
//0(n^2),0(1)
void BubbleSort(int *arry,int len)
{
assert(arry);
for(int i = 0;i < len -1;++i)
{
for(int j = len - 1;j >= i;--j)
{
if(arry[j] < arry[j-1])
{
int temp = arry[j];
arry[j] = arry[j - 1];
arry[j - 1] = temp;
}
}
}
}
//快速排序：我們快速排序的大概思路就是選擇一頭一尾的2個(gè)下標(biāo)/指針,然后我們利用指針選擇法
//將大數(shù)與小數(shù)集中排列。將我們所選的key值建為關(guān)鍵值，大于放左邊，小于放右邊。然后不斷縮小范圍就好了
//提高效率的辦法就是我們可以在當(dāng)前序列的值小于某個(gè)數(shù)值的時(shí)候我們選擇使用插入排序。
//這可以有效的提高我們排序的效率。
//一前一后只適用于數(shù)組。
//0（nlogn）,0(logn)
int _QuickSort(int* arry,int left,int right)
{
assert(arry);
if(left >= right)
return 0;
int tmp = arry[right];
int index = right;
--right;
while(left = tmp)
++right;
if(left < right)
{
swap(arry[left],arry[right]);
}
}
if(tmp <= arry[right])
{
swap(arry[right],arry[index]);
}
return right;
}
void QuickSort(int *arry,int left,int right)
{
assert(arry);
if(left < right)
{
int mid = _QuickSort(arry,left,right);
QuickSort(arry,mid+1,right);
QuickSort(arry,left,mid-1);
}
}
//快速排序：前后指針，我們選擇一個(gè)緊緊跟隨的2個(gè)指針，原理跟一前一后相同，知識(shí)進(jìn)行了大數(shù)小數(shù)的堆置、
//這樣的方法可以利用到指針中，當(dāng)然了，key值得選擇很重要，
//最壞的情況就是選擇到了有序數(shù)組的最大數(shù)/最小數(shù)，就會(huì)出現(xiàn)最壞的情況。
//選擇3數(shù)取中法可以有效地避免這個(gè)情況的出現(xiàn)。
void swap(int* arry,int left,int right)
{
int tmp;
tmp = arry[left];
arry[left] = arry[right];
arry[right] = tmp;
}
void QuickSort_On(int* arry,int left,int right)
{
int i,last;
if(left >= right)
return ;
swap(arry,left,(left+(right-left)/2));
last = left;
for(i = left +1;i <= right;++i)
{
if(arry[i] < arry[left])
swap(arry,++last,i);
}
swap(arry,left,last);
QuickSort_On(arry,left,last - 1) ;
QuickSort_On(arry,last +1,right);
}
//歸并排序：利用樹(shù)的分支然后在利用區(qū)間的整合，實(shí)現(xiàn)排序完成。
//每次我們確定一個(gè)區(qū)間（n/2），然后不斷進(jìn)行2分的拆分。
//在沒(méi)2個(gè)區(qū)間中我們進(jìn)行比較排序，對(duì)每個(gè)區(qū)間的首部進(jìn)行比較，然后規(guī)整到我們需要保存的數(shù)組中。
//最后我們通過(guò)不斷的拆分，不斷地歸并復(fù)制，就可以出現(xiàn)相對(duì)的排序序列了。
//0（nlogn）,0（n）
void Merge(int* arry,int* dest,int begin1,int end1,int begin2, int end2)
{
int index = begin1;
while(begin1 <= end1 && begin2 <= end2)
{
if(arry[begin1] < arry[begin2])
{
dest[index++] = arry[begin1++];
}
else
{
dest[index++] = arry[begin2++];
}
}
if(begin1 <= end1)
{
while(begin1 <= end1)
{
dest[index++] = arry[begin1++];
}
}
else
{
while(begin2 <= end2)
dest[index++] = arry[begin2++];
}
}
void _Merge(int* arry,int* dest, int left,int right)
{
//因?yàn)槭亲箝]右開(kāi)。
int mid = left+((right - left) /2);
if(left < right -1)
{
//int mid = left+((right - left)>>1);
_Merge(arry,dest,left,mid);
_Merge(arry,dest,mid+1,right);
Merge(arry,dest,left,mid,mid+1,right);
//memcpy(arry+left,dest+left,sizeof(int)* (right - left +1));
}
Merge(arry,dest,left,mid,mid+1,right);
memcpy(arry+left,dest+left,sizeof(int)* (right - left +1));
}
void MergeSort(int *arry,size_t size)
{
int* dest = new int[size];
_Merge(arry,dest,0,size-1);
//memcpy(arry,dest,sizeof(int)* (11));
delete[] dest;
}
總結(jié)：
創(chuàng)新互聯(lián)公司是一家專注于做網(wǎng)站、網(wǎng)站設(shè)計(jì)與策劃設(shè)計(jì),和平網(wǎng)站建設(shè)哪家好?創(chuàng)新互聯(lián)公司做網(wǎng)站,專注于網(wǎng)站建設(shè)十載,網(wǎng)設(shè)計(jì)領(lǐng)域的專業(yè)建站公司;建站業(yè)務(wù)涵蓋:和平等地區(qū)。和平做網(wǎng)站價(jià)格咨詢:18982081108
其中時(shí)間復(fù)雜度為nlogn的有快速排序，歸并排序，堆排序。其中快速排序最壞的情況是n^2,其余都是n^2,希爾排序介于n-n^2之間。
對(duì)于穩(wěn)定性來(lái)說(shuō)，冒泡排序，插入排序，歸并排序是穩(wěn)定的，其他的排序在不同的情況下穩(wěn)定性會(huì)不同。
對(duì)于空間復(fù)雜度來(lái)說(shuō)，快速排序的空間復(fù)雜度是0（logn），歸并排序是0（n）
下面是只能在限定條件里面使用的基數(shù)排序和計(jì)數(shù)排序：
計(jì)數(shù)排序:時(shí)間復(fù)雜度:O(N), 空間復(fù)雜度O(最大數(shù)-最小數(shù))
基數(shù)排序:時(shí)間復(fù)雜度:O(N*位數(shù))，空間輔助度O(N)
//基數(shù)排序：利用哈希桶原理把數(shù)據(jù)排序，可選擇從低位到高位或從高位到低位
//利用稀疏矩陣壓縮存儲(chǔ)進(jìn)行數(shù)據(jù)定位
int GetDigit(int* arr, size_t size)
{
int maxDigit = 1;
int maxNum = 10;
for (int i = 0; i < size; ++i)
{
if (arr[i] >= maxNum)
{
int count = maxDigit;
while (maxNum <= arr[i])
{
maxNum *= 10;
++count;
}
maxDigit = count;
}
}
return maxDigit;
}
void LSDSort(int* arr, size_t size)//從低位開(kāi)始排 MSD從高位開(kāi)始排
{
int counts[10] = { 0 };//存位數(shù)對(duì)應(yīng)數(shù)據(jù)個(gè)數(shù)
int startCounts[10] = { 0 };
int *bucket = new int[size];
int digit = 1;//表示先取各位
int maxDigit = GetDigit(arr, size);
int divider = 1;//除數(shù)
while (digit++ <= maxDigit)
{
memset(counts, 0, sizeof(int) * 10);
memset(startCounts, 0, sizeof(int) * 10);
for (int i = 0; i < size; ++i)
counts[(arr[i]/divider)% 10]++;
for (int i = 1; i < 10; ++i)
startCounts[i] = startCounts[i - 1] + counts[i - 1];
for (int i = 0; i < size; ++i)
{
bucket[startCounts[(arr[i] / divider) % 10]++] = arr[i];
}
divider *= 10;
memcpy(arr, bucket, sizeof(int)*size);
}
memcpy(arr, bucket, sizeof(int)*size);
delete[] bucket;
}
//計(jì)數(shù)排序
void CountSort(int *arr, size_t size,int len)
{
int* bitMap = new int[len];
memset(bitMap, 0, sizeof(int)*len);
for (int i = 0; i < size; ++i)
{
int index = arr[i] >>5;//除以32
int count = arr[i] % 32;
bitMap[index] |= (1 << count);
}
int index = 0;
for (int i = 0; i < len; ++i)
{
int count = 0;
while (count <32&&index這兩個(gè)排序的使用環(huán)境只能夠在特定的條件下使用，所以沒(méi)有納入常規(guī)的排序手法中，但是可以看出他的效率十分驚人。
分享標(biāo)題：【C/C++】排序總結(jié)
文章轉(zhuǎn)載：http://weahome.cn/article/jhjeio.html
重慶分公司
重慶分公司
