C语言--快速排序和归并排序

使用C语言实现快速排序和归并排序
  
  
快速排序

采用“分而治之”的思想。
起首选择一个基准pivot
对数据进行分割，将大于基准的元素放在左边，小于基准的元素放在右边
最后使用递归的方式，分别对左、右进行排序。
根据选取分割的方式不同，分为Hoare算法和Lomuto算法

1. void swap(int *a,int *b){
2.         int tmp = *a;
3.         *a=*b;
4.         *b=tmp;
5. }

复制代码

Lomuto算法

1. int partitionL(int arr[],int low, int high){
2.      int pivot=arr[high];
3.      int i=low-1;
4.      for(int j=low;j<=high-1;j++){
5.           if(arr[j]<=pivot){
6.              i++;
7.              swap(&arr[i],&arr[j]);
8.           }
9.      }
10.      swap(&arr[i+1],&arr[high]);       
11.      return i+1;
12. }
13. void quickSort(int arr[],int low,int high){
14.    if(low<high){
15.       int pivot = partitionL(arr, low, high);
16.       partitionL(arr, low, pivot-1);
17.       partitionL(arr, pivot+1, high);
18.    }
19. }

复制代码

Hoare算法

1. int partitionH(int arr[],int low, int high){
2.      int pivot = arr[(low+high)/2]
3.      int i=low-1;
4.      int j=high+1;
5.      while(1){
6.         do{i++;}while(arr[i]<pivot);
7.         do{j--;}while(arr[j]>pivot);
8.         if(i>=j){
9.             return i;
10.         }
11.         swap(&arr[i], &arr[j])
12.      }
13. }
14. void quickSortH(int arr[],int low, int high){
15.    if(low<high){
16.       int pivot = partitionL(arr, low, high);
17.       partitionL(arr, low, pivot);
18.       partitionL(arr, pivot+1, high);
19.    }
20. }

复制代码

归并排序

采用“分治”的思想，将一个大数列分为小的数列，在将有序的小数列组合，得到完全有序的数列。

1. // 合并两个有序的数组
2. void merge(int arr[], int low, int mid, int high){
3.      int n1= mid-low+1;
4.      int n2= high-mid;
5.      int *L = (int *)malloc(n1 * sizeof(int));
6.      int *R = (int *)malloc(n2 * sizeof(int));
7.      int i,j,k;
8.      for(i=0;i<n1;i++){
9.         L[i] = arr[low+i];
10.      }
11.      for(j=0;j<n2;j++){
12.         R[j] = arr[mid + 1 + j];
13.      }
14.      i = 0,j = 0, k=low;
15.      while(i<n1 && j<n2){
16.          if(L[i] <= R[j]){
17.             arr[k++] = L[i++];
18.          }else{
19.             arr[k++] = R[j++];
20.          }
21.      }
22.      while (i<n1) {
23.         arr[k++] = L[i++];
24.      }
25.      while (j<n2) {
26.         arr[k++] = R[j++];
27.      }
28.     free(L);
29.     free(R);
30. }
32. void mergeSort(int arr[], int low, int high){
33.     if(low < high){
34.         int mid = low + (high-low)/2;
35.         mergeSort(arr, low. mid);
36.         mergeSort(arr, mid+1, high);
37.         merge(arr, low, mid, high);
38.     }
39. }

复制代码

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。