經(jīng)典排序算法

1.?????? 冒泡排序

依次比較相鄰兩元素大小。如果按升序排列，較大元素放后面；如果按降序排列較小元素放后面。

　　　　

void BubbleSort(int *arr, int n){if(arr==NULL)return;for(int i=0; i<n-1; i++){for(j=0; j<n-1-i; j++){if(arr[j]>arr[j+1]){ //升序排列int temp=arr[j];arr[j]=arr[j+1];arr[j+1]=temp;}}} return; }

時間復(fù)雜度分析：

最佳情況：O(n)原始數(shù)組按序排列

最差情況：O(n^2)原始數(shù)組逆序排列

2.?????? 選擇排序

和冒泡排序思路幾乎一樣，唯一區(qū)別不是交換相鄰兩元素而是找出當(dāng)前未排序序列的最小（大）元素，與當(dāng)前未排序序列第一個元素交換。　　

　　　　　　

void SelectionSort(int *arr, int n){if(arr==NULL)return;for(int i=n-1; i>=0; i--){int maxIndex=i;for(j=i; j>=0; j--){if(arr[j]>arr[maxIndex]) //升序排列maxIndex=j;}int temp=arr[i];arr[i]=arr[maxIndex];arr[maxIndex]=temp;}return; }

?

時間復(fù)雜度分析：

?????? O(n^2)

3.?????? 插入排序

　　第一個元素默認是排序的，以后每選擇一個元素插入排序中。

? ? ? ? ? ?

void InsertSort(int *arr, int n){if(arr==NULL)return;for(int i=0; i<n; i++){int curVal=arr[i];int preIndex=i-1;while(preIndex>=0&&curVal<arr[preIndex]){arr[preIndex+1]=arr[preIndex];preIndex--;}arr[preIndex+1]=curVal;}return; }

?

時間復(fù)雜度分析：

最佳情況：O(n)原始數(shù)組有序排列

最壞情況：O(n^2)原始數(shù)組逆序排列

4.?????? 希爾排序（遞減增量排序算法）

希爾排序是對插入排序的改進。插入排序?qū)缀跻呀?jīng)拍好序的數(shù)據(jù)操作時，效率高，即可達到線性排序的效率；希爾排序是將待排序序列分割成若干子序列分別進行直接插入排序，待整個序列基本有序時，再對整體進行直接插入排序。

　　　　　　　　

void ShellSort(int *arr, int n){if(arr==NULL)return;int gap=n; //間隔while(true){ //每一步都是一個插入排序gap=gap/2;for(int i=0; i<gap; i++){for(int j=i+gap; j<n; j++){int temp=arr[j];int m;for(m=i-gap; m>=0 && arr[m]>temp; m=m-gap){arr[m+gap]=arr[m];}arr[m+gap]=temp;}}if(gap==1)break;}return; }

時間復(fù)雜度分析：

?????? O(nlogn)

5.?????? 快速排序

隨機選擇數(shù)組中的一個數(shù)，比選擇的數(shù)字小的數(shù)字移到數(shù)組左邊，比選擇數(shù)字大的移到數(shù)組右邊。

　　　　　　　　　　

void swap(int *a, int* b){ //交換兩個數(shù)字int temp;temp=*a;*a=*b;*b=temp;return; }void QuickSort(int data[], int start, int end){if(start>=end)return;int temp;//待排序的第最后一個元素作為基準(zhǔn)元素int small=start-1;for(int index=start; index<end; index++){if(data[index]<data[end]){small++;if(small!=index)swap(data[small], data[index]);}}small++;swap(data[small], data[end]);QuickSort(data[], start, small-1);QuickSort(data[],small+1, end);return; }

時間復(fù)雜度分析：

最佳情況：O(nlogn)每次正好中分

最差情況：分為1個元素和其它元素兩部分

6.?????? 歸并排序

包括分解和合并兩部分

合并相鄰有序子序列

（此圖轉(zhuǎn)載自博客：https://www.cnblogs.com/linjiaxin/p/7615196.html）

void MergeSortCore(int *data, int* copy, int start, int end){if(start==end){copy[start]=data[start];return;}int length=(start+end)/2;MergeSortCore(copy, data, start, start+length); //分解MergeSortCore(copy, data, start+length+1, end);int i=start+length;int j=end;int indexCopy=end;while(i>=start&& j>=start+length+1){ //合并if(data[i]>data[j])copy[indexCopy--]=data[i--];elsecopy[indexCopy--]=data[j--];}for(; i>=start; --i)copy[indexCopy--]=data[i];for(; j>=start; --j)copy[indexCopy--]=data[j];return; }void MergeSort(int *data, int length){if(data==NULL|| length<0)return;int* copy=new int[length];for(int i=0; i<length; i++)copy[i]=data[i];MergeSortCore(data, copy, 0, length-1);delete[] copy;return; }

時間復(fù)雜度分析：

?????? O(nlogn)

7.?????? 堆排序：

堆排序，就是以堆的方式去排序，什么是堆呢？滿足對任意一個父節(jié)點不大（小）于其子節(jié)點的完全二叉樹。大根堆用于升序排列，小根堆用于將序排列。

步驟：

?????? 將原始數(shù)組構(gòu)建成大（小）根堆；

將堆頂元素和最后一個元素進行交換，得到新的無序數(shù)組區(qū)域和新的有序數(shù)組區(qū)域；

重新調(diào)整無序數(shù)組區(qū)域為大（小）根堆，將堆頂元素和最后一個元素進行交換，直到排列完

?????? （對原理講解的很不錯的博客：https://blog.csdn.net/u013384984/article/details/79496052）

void swap(int &a, int &b){int temp=a;a=b;b=temp; }void AdjustHeap(int arr[], int nodeIndex, int n){int leftChild=2*nodeIndex+1;int rightChild=2*nodeIndex+2;int maxIndex=nodeIndex;if(leftChild<n && arr[maxIndex]<arr[leftChild])maxIndex=leftChild;if(rightChild<n && arr[maxIndex]<arr[rightChild])maxIndex=rightChild;if(maxIndex!=nodeIndex){swap(arr[maxIndex], arr[nodeIndex]);adjustHeap(arr, maxIndex, n);} }//大根堆，升序排列 void HeapSort(int arr[], int n){if(n==1) //直到無序區(qū)的元素個數(shù)為1return;//最后一個非葉子節(jié)點編號為n/2-1，從0開始計數(shù)for(int i=n/2-1; i>=0; i--)AdjustHeap(arr, i, n); //調(diào)整為大根堆swap(arr[0], nums[n-1]); //將堆頂與最后一個元素交換HeapSort(arr, n-1); //排序數(shù)組減一 }

時間復(fù)雜度分析：

?????? O(nlogn)

8.?????? 桶排序（基數(shù)排序）

找出最大的數(shù)

將所有待比較的數(shù)統(tǒng)一為同樣的位數(shù)長度，較短前面補0

從最低位開始，依次進行一次排序

int maxBit(int data[], int n){int maxData=data[0];for(int i=1; i<n; i++){if(maxData<data[i])maxData=data[i];}int maxn=0;while(maxData!=0){maxData/=10;maxn++;}return maxn; }void BucketSort(int data[], int n){int maxn=maxBit(data, n); //最大位數(shù)int temp=new int[n]; //臨時存儲int *count=new int[10]; //10個桶0-9int i,j,k;int radix=1;for(i=1; i<=maxn; i++){ //進行maxn次排序for(j=0; j<10; j++)//每次排序前初始化為0count[j]=0;for(j=0; j<n; j++){ //桶統(tǒng)計k=(data[j]/radix)%10;count[k]++;}for(j=1; j<10; j++)count[i]+=count[i-1]; //將temp中的位置依次分配給各個桶for(j=n-1; j>=0; j--){ //先占據(jù)后面的位置所以從后往前放。k=(data[j]/radix)%10;temp[count[k]-1]=data[j]; //放入到分配的桶count[k]--; //依次前移放入 }for(j=0; j<n; j++) //一次排序結(jié)果data[j]=temp[j];radix=radix*10; //調(diào)整桶基數(shù) }delete []temp;delete []count; }

時間復(fù)雜度分析

O(p(n+b)),其中n是待排元素個數(shù)，b是桶個數(shù)，p是排序的次數(shù)

轉(zhuǎn)載于:https://www.cnblogs.com/XZDSF/p/11239038.html

總結(jié)

以上是生活随笔為你收集整理的专题-经典排序算法的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。