赞
踩
挖坑法的思想:记第一个数为key,要调整key的位置,使得左边的都要比key的小,右边的数都比key的大。
记录下关键字key==begin,把28那个位置挖坑hole==begin
让end找到小于28(key)的数,把那个数放到hole坑中,然后让hole==end
再从左边begin找大于28(key)的数,把那个数放在hole中,然后让hole==begin
结束条件begin>=end调出循环。然后arr[hole]=key;
完成一趟的调整。
- //一趟挖坑
- int arr[]={5,3,2,6,7,4,9};
- int n=sizeof(arr)/sizeof(arr[0]);
- int begin=0;
- int end=n-1;
- while(begin<end)
- {
- while(begin<end&&arr[end]>=key)
- {
- end--;
- }
- arr[hole]==arr[end];
- hole==end;
- while(begin<end&&arr[begin]<=key)
- {
- begin++;
- }
- arr[hole]==arr[begin];
- hole=begin;
- }
- arr[hole]==key;
-
-

再分治思想,分成左边和右边。
用到分治递归,就要改变函数的参数,要有left和right
你们以为这样子快排就无敌了吗?不!当key每次取到的数都是最小或者最大,(也就是数组有序的情况下)它的时间复杂度会达到O(N^2)
那要怎么优化呢?三数取中法,就是创建一个函数,比较left,right,mid三个数,取大小是中等的数。然后把中等大小的数的下标返回出来,出来之后与begin(left)交换,为了确保不大改动原代码。
- //三数取中
- int GetMidIndex(int* a, int left,int right)
- {
- int mid = (left + right) / 2;
- if (a[mid] > a[left])
- {
- if (a[mid] <= a[right])
- {
- return mid;
- }
- if (a[mid] > a[right])
- {
- if (a[right] >= a[left])
- {
- return right;
- }
- else
- {
- return left;
- }
- }
- }
- if(a[mid]<=a[left])
- {
- if (a[left] <= a[right])
- {
- return left;
- }
- if (a[left] > a[right])
- {
- if (a[right] > a[mid])
- {
- return right;
- }
- else
- {
- return mid;
- }
- }
- }
- }

整体的代码如下:
- #define _CRT_SECURE_NO_WARNINGS 1
- #include<stdio.h>
- int GetMidIndex(int* a, int left,int right)
- {
- int mid = (left + right) / 2;
- if (a[mid] > a[left])
- {
- if (a[mid] <= a[right])
- {
- return mid;
- }
- if (a[mid] > a[right])
- {
- if (a[right] >= a[left])
- {
- return right;
- }
- else
- {
- return left;
- }
- }
- }
- if(a[mid]<=a[left])
- {
- if (a[left] <= a[right])
- {
- return left;
- }
- if (a[left] > a[right])
- {
- if (a[right] > a[mid])
- {
- return right;
- }
- else
- {
- return mid;
- }
- }
- }
- }
- void Swap(int* a, int* b)
- {
- int tmp = *a;
- *a = *b;
- *b = tmp;
- }
- //1.挖坑法的快速排序
- void QuickSort(int* a,int left,int right)
- {
- if (left >= right)//不能写成pivot==left,pivot-1与left不匹配,会报错
- {
- return;
- }
- int index = GetMidIndex(a, left, right);
- Swap(&a[index], &a[left]);
- int begin = left,end = right;
- int key = a[begin];//挖了一个关键字
- int pivot = begin;//挖了一个坑
- while (begin < end)
- {
- //右边找小,一定要先右边找小,放在pivot
- while (begin < end&&a[end] >= key)//在这里也要判断begin < end,因为这里面end--
- {
- end--;
- }
- //小的放在左边的坑里,然后形成新的坑位
- a[pivot] = a[end];
- pivot = end;
- //左边找大
- while (begin < end && a[begin] <= key)
- {
- begin++;
- }
- a[pivot] = a[begin];
- pivot = begin;
- }
- //begin==end
- a[pivot] = key;
-
- //[left,right]
- //[left,pivot-1] pivot [pivot+1,right]
- //如果左子区间和右子区间都有序,就全部有序。那就分治递归。
- QuickSort(a, left, pivot - 1);
- QuickSort(a, pivot+1, right);
- }
- void PRINT(int* a, int n)
- {
- for (int i = 0; i < n; i++)
- {
- printf("%d ", a[i]);
- }
- }
- int main()
- {
- int arr[] = { 5,6,8,9,3,1,4,7,5,1 };
- int n = sizeof(arr) / sizeof(arr[0]);
- QuickSort(arr, 0,n-1);
- PRINT(arr,n);
- return 0;
- }

注意:在QuickSort函数中,取到中等值的下标的时候,把中等值的位置与最左边的值交换一下。
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。