课程网站建设发展趋势,百度榜,企业宣传册设计与制作,网页设计网上培训班快速排序作为排序家族里面最为快捷的方式#xff0c;值得思考。我们将一个数组中的某一个数定为基点#xff0c;然后通过快速排序按照需求#xff08;假设升序#xff09;#xff0c;将比基点小的数丢在基点左边#xff0c;把比基点大的数丢在基点右边这样来将基点数的正… 快速排序作为排序家族里面最为快捷的方式值得思考。我们将一个数组中的某一个数定为基点然后通过快速排序按照需求假设升序将比基点小的数丢在基点左边把比基点大的数丢在基点右边这样来将基点数的正确位置找到。接着我们再对基点两边的数组分别进行快排以达到有序的目的。 举例实际分析如下 int data[6] {6,2,7,3,8,9}; int i leftj rightkey data[left]; 初始数组为6 2 3 7 8 9我们将基点数定位6进行第一次比较。 此时right 5left 0。先从右往左找寻比key小的数right 3时找到。将data[ left]赋值为data[right] - 3 2 7 3 8 9。 然后从左往右找比key大的数i 2时找到。我们将data[right]赋值为data[left] - 3 2 7 7 8 9。 左右找寻数的任务已经完成此时应该将key值放在正确位置去了但是这个位置是哪里现在还不知道因为左右标志位还不等但是下一次循环开始后发现left 和 right 在2的地方相等了。所以这个位置应该是2 - 3 2 6 7 8 9。这样一次排序完成了。 现在i 和 j 已经都变成了2而且6的正确位置已经找到了。但是按照算法的思路将这个数组分为左右两部分该怎么办我们的left和right派上了大用场。从left 到 i - 1为左边部分从j 1 到 right则为右半部分对这两部分进行递归快排最终可得到结果。 //
// main.cpp
// test
//
// Created by MadMarical on 15/11/20.
// Copyright (c) 2015年 com. All rights reserved.
//#include iostreamusing namespace std;int pData[] {6,2,7,3,8,9};void quickSort(int *p,int s,int t)
{int left,right;int key;left s,right t;key p[left];if (s t){return;}while (left ! right) //左右标志不等在数组内寻找{while (left ! right p[right] key) //因为是升序在数组里从右往左找寻一个比key小的数。{right--;}p[left] p[right];while (left ! right p[left] key){left;}p[right] p[left];}p[left] key;quickSort(p, s, left - 1);quickSort(p, right 1, t);
}int main(int argc, const char * argv[])
{quickSort(pData, 0, 5);coutpData[0] pData[1] pData[2] pData[3] pData[4] pData[5]endl;return 0;
} 反思 1.如果使用swap进行交换在代码理解上会减轻不少。 2.快速排序中的判断方法和递归调用值得深思网上的许多答案也是模棱两可还是要自己理解比较靠谱。 转载于:https://www.cnblogs.com/thewaytomakemiracle/p/4981054.html
