列出网站开发建设的步骤,株洲定制网站建设,深圳搜豹网站建设公司,免费发帖推广网站目录
一、快速排序是什么#xff1f;
二、左右指针法
1.实现原理
2.代码如下#xff1a;
三、挖坑法
1.实现原理
2.代码如下#xff1a;
四、前后指针法
1.实现原理
2.代码如下#xff1a;
五、三数取中
1.实现思想
2.代码如下#xff1a; 3.使用方法
总结…目录
一、快速排序是什么
二、左右指针法
1.实现原理
2.代码如下
三、挖坑法
1.实现原理
2.代码如下
四、前后指针法
1.实现原理
2.代码如下
五、三数取中
1.实现思想
2.代码如下 3.使用方法
总结 前言 快排是公认的排序效率之王加上三数取中与小区间优化更是无人能敌。 一、快速排序是什么 快排分为三种实现方式 ①左右指针法 ②挖坑法 ③前后指针法 其中左右指针与挖坑法实现原理差不多一样只是挖坑法多创建一个临时变量存储坑中的数据它们俩都是选大的的通过自己的方式放在后面选出小的通过自己的方式放前面通过递归就可将整个数组进行排序。 前后指针法同样是选大的放后面选小的放前面但是与上面两个不同的是它只从一头开始遍历。 二、左右指针法
1.实现原理 ① 定义两个指针一个从左边遍历一个从右边遍历。 ② 定义一个key值用来做比较的基准值。 ③ 如果key是最左边的值那么就让right先向左找小值反之就让left先找大值。 目的在left与right相遇时在与key值交换时能够交换大值小值否则会出现数据错误。 ④ 假定key值定义为最左边的数字 right向左走找比key值大的数据找到后停下 left向右走找比key值小的数据找到后停下 此时交换left与right对应的值循环往复直至left与right相遇。 ⑤ 相遇后将相遇点与keyi对应的数据进行交换此时数组将会达到key左边的数字都小于key右边的数字都大于key后续通过递归可实现整个数组的排序。 2.代码如下
#include stdio.hvoid swap(int* x, int* y)
{int tmp *x;*x *y;*y tmp;
}
// 左右指针法
void QuickSort1(int* arr, int begin, int end)
{if (begin end){return;}int left begin;int right end;int keyi left;while (left right){// right向左找小while (left right arr[right] arr[keyi]){right--;}while (left right arr[left] arr[keyi]){left;}// key的大值与小值进行换位swap(arr[left], arr[right]);}// 左右指针相遇与key换位int meeti left;swap(arr[meeti], arr[keyi]);QuickSort1(arr, begin, meeti - 1);QuickSort1(arr, meeti 1, end);
}
int main()
{int arr[] { 5,3,6,9,8,7,2,0,1,4 }; size_t len sizeof(arr) / sizeof(arr[0]);QuickSort1(arr, 0, len - 1);return 0;
}
三、挖坑法
1.实现原理 挖坑法与左右指针法大致相同。 ① 选出一个key值并将其所在的位置定为坑坑可被覆盖 - 放数据坑中的数据被保存在了key中 ② 定义两个指针一个从左边遍历一个从右边遍历。 ③同左右指针法相同 如果key是最左边的值那么就让right先向左找小值反之就让left先找大值。 目的在left与right相遇时在与key值交换时能够交换大值小值否则会出现数据错误。 ④ 假定key值定义为最左边的数字 right找到比key值大的数据停下将此数入坑同时right所在的位置变为新坑 left向右走找比key值小的数据找到后停下将此数入坑同时left所在的位置变为新坑 循环此过程直至两指针相遇。 ⑤ 将key值入坑此时数组将会达到key左边的数字都小于key右边的数字都大于key后续通过递归可实现整个数组的排序。 2.代码如下
// 挖坑法
void QuickSort2(int* arr, int begin, int end)
{if (begin end){return;}int left begin;int right end;int key arr[left];int pivot left;while (left right){// right向左找小while (left right arr[right] key){right--;}// 入坑更新坑位arr[pivot] arr[right];pivot right;// left向右找大while (left right arr[left] key){left;}arr[pivot] arr[left];pivot left;}// 相遇key值入坑arr[pivot] key;QuickSort2(arr, begin, pivot - 1);QuickSort2(arr, pivot 1, end);
}// 挖坑法
void QuickSort2(int* arr, int begin, int end)
{if (begin end){return;}int left begin;int right end;int key arr[left];int pivot left;while (left right){// right向左找小while (left right arr[right] key){right--;}// 入坑更新坑位arr[pivot] arr[right];pivot right;// left向右找大while (left right arr[left] key){left;}arr[pivot] arr[left];pivot left;}// 相遇key值入坑arr[pivot] key;QuickSort2(arr, begin, pivot - 1);QuickSort2(arr, pivot 1, end);
}
int main()
{int arr[] { 5,3,6,9,8,7,2,0,1,4 }; size_t len sizeof(arr) / sizeof(arr[0]);QuickSort1(arr, 0, len - 1);return 0;
} 四、前后指针法
1.实现原理 ① 定义两个指针一前(cur)一后(prev)。 ② 定义一个key值用来作为单趟排序的基准值。 ② 让前面的指针继续向前遍历如果找到比key值小的prev后与其交换。 ③ 重复②直至cur到达数组末尾交换prev与keyi对应的数据。 ④ 此时数组将会达到key左边的数字都小于key右边的数字都大于key后续通过递归可实现整个数组的排序。 2.代码如下
// 前后指针法
void QuickSort3(int* arr, int begin, int end)
{if (begin end){return;}int left begin;int right end;int key arr[left];int prev left;int cur prev 1;while (cur end){if (arr[cur] key prev ! cur)// 减少不必要的swap{swap(arr[prev], arr[cur]);}cur;}swap(arr[prev], arr[begin]);QuickSort3(arr, begin, prev - 1);QuickSort3(arr, prev 1, end);
}int main()
{int arr[] { 5,3,6,9,8,7,2,0,1,4 }; size_t len sizeof(arr) / sizeof(arr[0]);QuickSort3(arr, 0, len - 1);return 0;
}
五、三数取中
1.实现思想 当待排序数组本来是逆序时快排效率将降到最低为O(N2)每次都许哟啊对每个数进行交换位置2次所以产生了三数去中的方法 取得数组最开始、最末尾、最中间中的中间值来平衡key值。 2.代码如下
// 三数取中
int GetMidIndex(int* arr, int begin, int end)
{int mid (end - begin) / 2 begin;if (arr[begin] arr[end]){// begin end midif (arr[mid] arr[end]){return end;}// mid begin endelse if (arr[mid] arr[begin]){return begin;}// begin mid endelse{return mid;}}// end beginelse{// mid end beginif (arr[mid] arr[end]){return end;}//end begin midelse if(arr[mid] arr[begin]){return begin;}else{return mid;}}
} 3.使用方法 在取key值时仍可继续取left位置的值但是在此之前做一次交换即可。 int index GetMidIndex(arr, begin, end);swap(arr[index], arr[left]);int key arr[left]; 总结 抓住快排的思想要点加上调试即可快速实现出排序算法。
