排序算法代碼總結

文章目錄

• 排序算法代碼總結
• • 前言
  • • 直接插入排序
    • 折半插入排序
    • 冒泡排序
    • 快速排序
    • 簡單選擇排序
    • 堆排序
    • 歸并排序
  • 排序算法比較

前言

以下排序方法都是從1至n的排序

int main() {int n;int a[10010];//輸入scanf("%d",&n);for(int i=1;i<=n;i++){scanf("%d",&a[i]);}//直接插入排序InsertSort(a, n);//折半插入排序//InsertSort2(a, n);//冒泡排序//BubbleSort(a, n);//快速排序// QuickSort(a, 1, n);//簡單選擇排序//SelectSort(a, n);//堆排序//HeapSort(a, n);//歸并排序//MergeSort(a, 1, n);//輸出for(int i=1;i<=n;i++){printf("%d ", a[i]);}return 0; }

直接插入排序

基本思想：對于有 n 個初始元素的序列，將第 2 至 n 個元素依次插入前面已排好序的子序列中，從而使序列整體有序

void InsertSort(int a[], int n) {int i,j;for(i=2;i<=n;i++)//將a[2]-a[n]依次插入前面已排序序列{if(a[i]<a[i-1])//a[i]值比前驅小，將其插入有序表中{a[0]=a[i]; //a[0]不存儲值，只起輔助交換作用for(j=i-1;a[0]<a[j];j--)//從后往前查找待插入的位置a[j+1]=a[j];a[j+1]=a[0];//插入找到的位置}} }

折半插入排序

折半插入排序是在直接插入排序算法上的改進，由于是順序存儲的線性表，所以查找有序子表時可以用折半查找來實現。確定待插入位置后，就可統一地向后移動元素

void InsertSort2(int a[], int n) {int i,j,low,mid,high;for(i=2;i<=n;i++)//將a[2]-a[n]依次插入前面已排序序列{a[0]=a[i]; //用a[0]暫存a[i]的值low=1;high=i-1; //設置折半查找的范圍while(low<=high){mid = (low+high)/2;if(a[mid]>a[0])//查找左半子表high=mid-1;else //查找右半子表low=mid+1;}for(j=i-1;j>=high+1;j--) //統一后移元素{a[j+1]=a[j];}a[high+1]=a[0]; //將值插入對應位置} }

冒泡排序

基本思想：從后往前兩兩比較相鄰元素的值，若為逆序則交換它們，直到序列比較完。

void BubbleSort(int a[], int n) {bool flag;//一趟冒泡是否發生交換的標志int tmp; //用于輔助交換的元素for(int i=1;i<n;i++)//n-1趟冒泡{flag=false;for(int j=n;j>i;j--)//一趟冒泡過程{if(a[j-1]>a[j])//逆序則交換{tmp=a[j-1];a[j-1]=a[j];a[j]=tmp;flag=true;}}if(flag==false)//一趟冒泡沒有交換，則序列已經有序return;} }

快速排序

基本思想：選取一個記錄（一般選取第一個記錄）作為樞紐（哨兵），然后將所有關鍵字比它小的記錄都放在它的位置之前，將所有關鍵字比它大的記錄都放在它的位置之后。由此，以該 “哨兵” 記錄最后所落的位置 i 為分界線，將整個序列分割成兩個子序列，對子序列繼續重復上述操作。

int Partition(int a[], int low, int high) {int tmp = a[low]; //通常將第一個元素當成哨兵while(low < high){while(low<high && a[high]>=tmp)//比哨兵小的元素移動到左邊high--;a[low] = a[high];while(low<high && a[low]<=tmp)//比哨兵大的元素移動到右邊low++;a[high] = a[low];}a[low] = tmp; //哨兵放到最終位置return low; } void QuickSort(int a[], int l, int r) {if(l<r){int p = Partition(a, l, r); //尋找哨兵QuickSort(a, l, p-1); //分割為兩個子序列，再分別排序QuickSort(a, p+1, r);} }

簡單選擇排序

基本思想：第 i 趟在后面 n-i+1 個待排序元素中選取關鍵字最小的元素，作為有序子序列的第 i 個元素，直到 n-1 趟做完，待排序元素只剩下一個，就不用再選了。

void SelectSort(int a[], int n) {int min=0,tmp=0;//記錄位置的元素，輔助元素for(int i=1;i<n;i++){min=i;//記錄最小元素的位置for(int j=i+1;j<=n;j++)//選出最小元素{if(a[j]<a[min]){min=j; //更新最小元素位置}}if(min!=i) //找到最小元素則交換{tmp=a[i];a[i]=a[min];a[min]-a[i];}} }

堆排序

堆是具有下列性質的完全二叉樹：每個結點的值都小于或等于其左右孩子結點的值（稱為小根堆），或每個結點的值都大于或等于其左右孩子結點的值（稱為大根堆）。堆采用一維數組存儲。

堆排序的基本思想：首先將待排序的記錄序列構造成一個堆，此時，選出了堆中所有記錄的最小者，然后將它從堆中移走，并將剩余的記錄再調整成堆，這樣又找出了次小的記錄，以此類推，直到堆中只有一個記錄。

//調整 void HeapAdjust(int a[], int k, int n) {int top = a[k]; //暫存子樹的根結點for(int i=2*k;i<=n;i*=2)//沿k較大的子結點向下篩選{if(i<n && a[i]>a[i+1])//取k較小的子結點的下標i++;if(top<=a[i]) //篩選結束break;else{a[k]=a[i]; //將a[i]調整到雙親結點上k=i; //修改k值，繼續篩選}}a[k] = top; //將調整前的堆頂記錄插入到k位置 } //建小根堆 void HeapSort(int a[], int n) {for(int i=n/2; i>0; i--)//初始化小根堆{HeapAdjust(a, i, n);}int tmp=0;for(int i=n;i>1;i--)//n-1調整{tmp = a[1];a[1] = a[i];a[i] = tmp; //將堆頂記錄與未排序的最后一個記錄交換HeapAdjust(a, 1, i-1);//重新調整為小根堆} }

如果要建立大根堆，只需要把篩選的條件反過來即可

if(i<n && a[i]<a[i+1])//取k較大的子結點的下標i++; if(top>=a[i]) //篩選結束break;

歸并排序

基本思想：設初始序列含有 n 個記錄，則可看成 n 個有序的子序列，每個子序列長度為 1。

兩兩合并，得到 $?n/2?$個長度為 2 或 1 的有序子序列。

再兩兩合并，……如此重復，直至得到一個長度為 n 的有序序列為止。

int b[10010]; //輔助數組B //歸并函數 void Merge(int a[], int low, int mid, int high) {for(int k=low;k<=high;k++)//將A所有元素復制到B{b[k]=a[k];}int i,j,k;for(i=low,j=mid+1,k=i; i<=mid && j<=high; k++){//比較B中左右兩段的元素，將較小值復制到Aif(b[i]<=b[j])a[k]=b[i++];elsea[k]=b[j++];}while(i<=mid) //若第一段還有元素，復制到A中a[k++]=b[i++];while(j<=high) //若第二段還有元素，復制到A中a[k++]=b[j++]; } //歸并排序 void MergeSort(int a[], int low, int high) {if(low<high){int mid = (low+high)/2; //找到序列中點MergeSort(a, low, mid); //左側序列遞歸排序MergeSort(a, mid+1, high); //右側序列遞歸排序Merge(a, low, mid, high); //歸并} }

歸并排序需要一個輔助數組 B，其長度與原數組 A 相同即可。

排序算法比較

總結

以上是生活随笔為你收集整理的排序算法代码总结的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。