赞
踩
归并排序:
思想为:在对待排序列设置一个中心点,以此为界左右进行拆分。在左子序列和右子序列递归执行上述过程,直到每个序列只有一个元素,拆分不动为止。
然后对相邻元素进行合并。待合并完成为一个大序列后,对相邻的大序列递归执行这个过程,到整个序列的左、右序列合并完了,整个排序便完了。
合并思想为:搞两个指针分别指向左、右子序列的头元素。开辟一个新数组存放结果,大小等同于左右子序列的和。通过俩指针逐个比较元素大小,对于升序而言,左右序列中哪个小就将小的那个放到新数组中。已经放到结果数组中的序列指针记得前移,当然结果数组指针也要前移。重复这一过程,直到左或右序列中指针已经到底了。把剩下的那个序列中元素全部移到结果数组中即可。
- #include <stdio.h>
- #include <stdlib.h>
- #include <string.h>
-
- void display(int arr[], int low, int high);
- void merge_sort(int arr[], int low, int high);
- void merge(int arr[],int low, int mid, int high);
-
- int main(int argc, char * argv[])
- {
- int arrtosort[] = {67,13,20,11,43,9,4,17};
- int len = (int)(sizeof(arrtosort)/sizeof(int));
- printf("len is: %d\n",len);
- merge_sort(arrtosort, 0, len-1);
-
- display(arrtosort, 0, len-1);
- }
-
- void display(int arr[], int low, int high)
- {
- int i = 0;
- for(i = low;i <= high; i++)
- {
- printf("%d ",arr[i]);
- }
- printf("\n");
- }
-
- void merge_sort(int arr[], int low, int high)
- {
- if (low >= high)
- return;
- int mid = (low + high)/2;
- merge_sort(arr, low, mid);
- merge_sort(arr, mid+1, high);
- printf("before merge: ");
- display(arr, low, high);
- merge(arr, low, mid, high);
- }
-
- void merge(int arr[],int low, int mid, int high)
- {
- int len = high - low + 1;
- int i = low, j = mid + 1;
- int k = 0;
- int tmp[len];
- while(i <= mid && j <= high)
- {
- if(arr[i] <= arr[j]){
- tmp[k++] = arr[i++];
- }
- else {
- tmp[k++] = arr[j++];
- }
- }
- while(i > mid && j <= high){
- tmp[k++] = arr[j++];
- }
- while(j > high && i <= mid){
- tmp[k++] = arr[i++];
- }
-
- int *add = tmp;
- memcpy(&arr[low],add,sizeof(tmp));
- // for(int i = 0;i <= len-1;i++)
- // arr[low+i] = tmp[i];
- printf("after merge: ");
- display(arr, low, high);
- }
快速排序:
在对待排序列选一个基准元素,考虑到方便第一个元素就行,备份此基准元素值。用两个指针分别指向原序列的头和尾。对于升序,用尾指针元素和基准值比较,如大等于基准值则尾指针前移,直到尾指针元素小于基准值或头尾指针相等。此时把尾指针元素copy到基准值元素的位置。当然原头指针元素既已被覆盖,头指针要后移。
现在尾指针元素已经被copy,相当于尾指针元素位置也空出来了,现在是对头指针元素进行操作的时候了。与尾指针相反,用头指针元素和基准值比较,如小等于基准值则头指针后移,直到头指针元素大于基准值或头尾指针相等。此时把头指针元素copy到尾指针元素的位置。当然尾指针元素既已被覆盖,尾指针要前移。
现在头指针/尾指针元素都被移动过了,重复上述过程:用尾指针元素和基准值比较。。,用头指针元素和基准值比较。。。直到头尾指针相等,此时把之前被覆盖掉的基准元素填入该头指针的位置,这轮排序完结。
以当前基准元素为止分割元序列为两个序列,分别重复上述整个过程(递归调用quick_sort)。
左侧子序列:
右侧子序列:
当整个原序列已被分割到单个元素时(也是quick_sort退出条件),所有排序已完成。
- #include <stdio.h>
- #include <stdlib.h>
-
- void quick_sort(int a[], int low, int high)
- {
- int i, j, pivot;
- if (low < high){
- pivot = a[low];
- i = low;
- j = high;
- while(i<j)
- {
- while(i<j && a[j]>=pivot)
- j--;
- if(i<j)
- a[i++]=a[j];
- while(i<j && a[i]<pivot)
- i++;
- if(i<j)
- a[j--]=a[i];
- }
- a[i] = pivot;
- display(a, low, high);
- quick_sort(a, low, i-1);
- quick_sort(a, i+1, high);
- }
- }
-
- void display(int a[],int low,int high)
- {
- int i = 0;
- for (i = low;i <= high; i++)
- printf("%d ",a[i]);
- printf("\n");
- }
-
- int main(int argc,char* argv[])
- {
- int arrtosort[] = {10,2,3,7,9,1,4,5,6,11,32,8};
- int len = 0;
- printf("sizeof arrtosort: %d\n", len = (int)(sizeof(arrtosort)/sizeof(int)));
- quick_sort(arrtosort, 0, len-1);
- display(arrtosort, 0, len-1);
- return 0;
- }
快排在空间复杂度上更胜于归并。归并需要额外空间,而快排直接在原序列上操作。
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。