快速排序的总结-创新互联
快速排序的思想是分而治之,利用递归达到快速排序的效果
创新互联公司公司2013年成立,是专业互联网技术服务公司,拥有项目网站设计、成都网站建设网站策划,项目实施与项目整合能力。我们以让每一个梦想脱颖而出为使命,1280元申扎做网站,已为上家服务,为申扎各地企业和个人服务,联系电话:18980820575首先要选定一个基准数,一般选择最左边的数为基准数,排序的目标就是让这个基准数的左边全小于这个基准数,右边全大于这个基准数。然后以这个基准数为分隔线,在左右两侧再次调用这个排序的函数,直到全部有序。简述过程:
以 8 9 4 7 2 6 选
1. 选择两个哨兵 i,j 分别指向8,6,基准数为8
2.从j哨兵开始,因为j指向的6小于基准数8,不符合j指向的数都要大于8的要求,所以将j指向的数覆盖i指向的数,同时i指向的数变成9
6 9 4 7 2 6
3.此时i指向9大于基准数8,不符合基准数左边的都要小于基准数,右边的都要大于基准数,所以i指向的数覆盖j指向的数,同时j--,j指向7
6 9 4 7 2 9
重复以上步骤,直到 哨兵i 和 哨兵j相遇
4.最后一步将基准值放到中间
代码实现:
void QuickSort(int a[], int low, int high)
{
int i = low, j = high;//每次i,j都指向最低一个元素,和最高一个元素
int temp = a[low];//每次选择最左边的数为基准数
while(i < j)//每次循环结束的条件是 i == j
{
while(i < j && a[j] >= temp) j--;//先从左边开始,找到小于基准数的数
if(i < j){
a[i] = a[j];
i++;
}//和i指向的数交换
while(i < j && a[i] <= temp) i++;//找到基准数左边大于基准数的数
if(i < j){
a[j] = a[i];
j--;
}//换到基准数右边去
}//以上执行完后,将基准数放到中间
a[i] = temp;
if(low < i)//如果是基准数左边的话
QuickSort(a, low, i-1);//将最高位i-1
if(i < high)//如果是基准数右边的话
QuickSort(a, j+1, high);//最低位为基准位+1
}
另外有需要云服务器可以了解下创新互联scvps.cn,海内外云服务器15元起步,三天无理由+7*72小时售后在线,公司持有idc许可证,提供“云服务器、裸金属服务器、高防服务器、香港服务器、美国服务器、虚拟主机、免备案服务器”等云主机租用服务以及企业上云的综合解决方案,具有“安全稳定、简单易用、服务可用性高、性价比高”等特点与优势,专为企业上云打造定制,能够满足用户丰富、多元化的应用场景需求。
新闻标题:快速排序的总结-创新互联
链接地址:http://pwwzsj.com/article/hdjss.html