這里,匯總了常見的排序算法具體代碼實現。使用C語言編寫。
排序算法實現
- 插入排序
- 冒泡排序
- 選擇排序
- 快速排序
- 希爾排序
- 歸并排序
插入排序
#include <stdio.h>
#include <stdlib.h>void InsertSort(int arr[],int n){int i,j,temp;for(i = 1;i < n;i++){ //將各元素插入已排好的序列中if(arr[i] < arr[i-1]){ //若當前元素小于前驅temp = arr[i]; //暫存當前元素for(j = i-1;j >= 0 && arr[j] > temp;j--) //檢查前面所有排好的元素arr[j+1] = arr[j]; //所有大于temp的元素后移arr[j+1] = temp; //復制到插入位置(j+1:j--多減了一個要加回來)}}
}int main()
{int a[] = {12,32,61,5,9,63,89,2};for(int i=0;i<8;i++)printf("%d ",a[i]);InsertSort(a,8);printf("\n");for(int i=0;i<8;i++)printf("%d ",a[i]);return 0;
}
冒泡排序
#include <stdio.h>
#include <stdlib.h>void bubbleSort(int arr[],int n){for(int i=0;i<n-1;i++){//外層循環,n個元素需要循環n-1次for(int j=0;j<n-1-i;j++){ //內層循環,n個元素第i趟比較n-i次if(arr[j]>arr[j+1]){ //將較大的元素后移int temp = arr[j+1];arr[j+1] = arr[j];arr[j] = temp;}}}
}int main()
{int a[] = {12,32,61,5,9,63,89,2};for(int i=0;i<8;i++)printf("%d ",a[i]);bubbleSort(a,8);printf("\n");for(int i=0;i<8;i++)printf("%d ",a[i]);return 0;
}
選擇排序
#include <stdio.h>
#include <stdlib.h>void selectSort(int a[],int n){int i,j,min = 0;for(i=0;i<n-1;i++){min = i;for(j=i+1;j<n;j++){if(a[j]<a[min]){ //尋找最小的數min = j; //尋找最小的索引保存}}if(i!= min){int tmp = a[i];a[i] = a[min];a[min] = tmp;}}
}int main()
{int a[] = {12,32,61,5,9,63,89,2};for(int i=0;i<8;i++)printf("%d ",a[i]);selectSort(a,8);printf("\n");for(int i=0;i<8;i++)printf("%d ",a[i]);return 0;
}
快速排序
#include <stdio.h>
#include <stdlib.h>void quickSort(int a[],int begin,int end){if(begin>=end) return; //遞歸結束條件int i = begin,j = end,flag = a[i],tmp = 0; //第一個為基準while(i!=j){while((i<j)&&(a[j]>flag)) j--; //從最后一個元素出發,每次循環j--,直到找到比flag小的數字,記錄下標while((i<j)&&(a[i]<=flag)) i++; //從開頭元素出發,每次循環i++,直到找到比flag大的數字,記錄下標if(j>i){ //交換tmp = a[i];a[i] = a[j];a[j] = tmp;}}a[begin] = a[i];a[i] = flag; //交換基準數與i和j相遇的位置的數quickSort(a,begin,i-1); //左子數組遞歸quickSort(a,i+1,end); //右子數組遞歸
}int main()
{int a[] = {12,32,61,5,9,63,89,2};for(int i=0;i<8;i++)printf("%d ",a[i]);quickSort(a,0,7);printf("\n");for(int i=0;i<8;i++)printf("%d ",a[i]);return 0;
}
希爾排序
#include <stdio.h>
#include <stdlib.h>void shellSort(int a[], int n){int i,j,gap; // gap為步長,每次減為原來的一半for (gap = n / 2; gap > 0; gap /= 2){ // 共gap個數組,對每一組都執行直接插入排序for (i = 0; i < gap; i++) {for (j = i + gap; j < n; j += gap){ // 如果a[j]<a[j-gap],則尋找a[j]位置,并將后面的位置都后移if (a[j] < a[j - gap]){int tmp = a[j];int k = j - gap;while (k >= 0 && a[k] > tmp){a[k + gap] = a[k];k -= gap;}a[k + gap] = tmp;}}}}
}int main()
{int a[] = {12,32,61,5,9,63,89,2};for(int i=0;i<8;i++)printf("%d ",a[i]);shellSort(a,8);printf("\n");for(int i=0;i<8;i++)printf("%d ",a[i]);return 0;
}
歸并排序
#include <stdio.h>
#include <stdlib.h>void Merge(int arr[], int tmp[], int start,int mid, int end){//合并小組并排序int i = start; //i標識,左小組的第一個元素位置int j = mid + 1;//j標識,右小組的第一個元素位置int k = start; //tmp當前小組存放的起始位置while (i < mid + 1 && j < end + 1){//左小組越界或右小組越界才能退出if (arr[i] <= arr[j])tmp[k++] = arr[i++];elsetmp[k++] = arr[j++];}while (j < end + 1){ //如果右邊小組沒有越界tmp[k++] = arr[j++];}while (i < mid + 1){ //如果左邊小組沒有越界tmp[k++] = arr[i++];}for (i = start; i <= end; i++){arr[i] = tmp[i];}
}void MergeS(int arr[], int tmp[], int start, int end){//劃分小組,現在沒有endif (start < end){int mid = (start+end)/2;MergeS(arr, tmp, start, mid);MergeS(arr, tmp, mid + 1, end);Merge(arr, tmp, start, mid, end);}
}void mergeSort(int arr[], int len){int *tmp = (int *)malloc(sizeof(int)*len);//開了一個排序后結果保存的臨時數組MergeS(arr, tmp, 0, len - 1);//嵌套調用free(tmp);
}int main()
{int a[] = {12,32,61,5,9,63,89,2};for(int i=0;i<8;i++)printf("%d ",a[i]);mergeSort(a,8);printf("\n");for(int i=0;i<8;i++)printf("%d ",a[i]);return 0;
}
不同排序算法之間的比較:
以上屬個人見解。
??希望對您有幫助,您的支持是我創作最大的動力!