| 网站首页 | 业界新闻 | 群组 | 交易 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
共有 272 人关注过本帖, 1 人收藏
标题:快速排序法(Quick_sort)详解
只看楼主 加入收藏
lyb661
Rank: 20Rank: 20Rank: 20Rank: 20Rank: 20
等 级:版主
威 望:12
帖 子:43
专家分:61
注 册:2018-12-12
结帖率:100%
  问题点数:0  回复次数:2   
快速排序法(Quick_sort)详解
快速排序法(Quick_sort)详解
快速排序法与其他排序如冒泡排序法、插入排序法、选择排序法有所不同,它不是用相邻元素两两比较使大数不断下沉或者小数不断上浮。而是用一个元素做界限,数值比它大的元素分为一组,数值小于它的元素分为另一组,至于两个组内的元素排列顺序它并不关注。做好这两个组后,利用递归法,对这两个数值一大一小的两部分以一个元素为界限再次分组。这样不断细分下去,元素最后做到有序。现在上代码:

void quick_sort(int a[],int low,int high)
{
    if(low >= high)
        return;

    int i = low,j = high,k = a[i];
    while( i < j )               //k一般取数组的第一个元素
    {
        while(i<j && a[j] >= k)
            j--;                //利用循环,由后向前检查元素的值,直到遇见比k小的数
        if(i<j) a[i] = a[j];    //把这个元素交换到k的前面

        while(i<j && a[i] <= k)
            i++;                //利用循环,由前向后检查元素的值,直到遇见比k大的数
        if(i<j) a[j] = a[i];    //把这个元素交换到k的后面
    }
    print_arr(a,high+1);

    a[i] = k;                    //a[i]在前面交换中已经被覆盖现在恢复它,目前i与j是相等的
    quick_sort(a,low,i-1);       //利用递归再分组……
    quick_sort(a,i+1,high);
}


//现在把程序完整代码附在下面

#include <iostream>

using namespace std;

void print_arr(int a[],int n)
{
    for(int i=0;i<n;i++){
        if(i>0)
            cout<<' ';
        cout<<a[i];
    }
}

void quick_sort(int a[],int low,int high)
{
    if(low >= high)
        return;

    int i = low,j = high,k = a[i];
    while( i < j )              
    {
        while(i<j && a[j] >= k)
            j--;               
        if(i<j) a[i] = a[j];   

        while(i<j && a[i] <= k)
            i++;               
        if(i<j) a[j] = a[i];   
    }

    a[i] = k;                  
    quick_sort(a,low,i-1);     
    quick_sort(a,i+1,high);
}


int main()
{
    int a[]={22,18,43,56,97,88,69};
    int n=sizeof a/sizeof a[0];
    quick_sort(a,0,n-1);
    print_arr(a,n);
    return 0;
}
2019-01-23 21:00
幽竹烟雨
Rank: 2
来 自:SunGalaxy
等 级:论坛游民
威 望:3
帖 子:40
专家分:82
注 册:2018-11-9
  得分:0 
这个嘛,两行代码就OK了
2019-01-31 12:18
幽竹烟雨
Rank: 2
来 自:SunGalaxy
等 级:论坛游民
威 望:3
帖 子:40
专家分:82
注 册:2018-11-9
  得分:0 
#include<bits/stdc++.h>
int main(){int a[8]={22,18,43,56,97,88,69};std::sort(a,a+7);for(int i=-1;i<6;i++,std::cout<<a[i]<<" "){}}
2019-01-31 12:19







关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.067138 second(s), 9 queries.
Copyright©2004-2019, BCCN.NET, All Rights Reserved