快速排序法

题外话:昨天开始准备C语言计算机二级,发现门外汉看还是有困难的,尤其是数据结构方面,看来要好好研究了。

快速排序法借用书上和百度的解释

在待排序的n个元素中取一个元素Key(通常取第一个元素),以元素Key作为分割标准,把所有小于Key元素的数据元素都移到K前面,把所有大于K元素的数据元素都移到K后面。这样,以K为分界线,把线性表分割为两个子表,这称为一趟排序。然后,对K前后的两个子表分别重复上述过程。继续下去,直到分割的子表的长度为1为止,这时,线性表已经是排好序的了。

快速排序的算法是:
1)设置两个变量i、j,排序开始的时候:i=0,j=N-1;
2)以第一个数组元素作为关键数据,赋值给key,即key=A[0];
3)从j开始向前搜索,即由后开始向前搜索(j--),找到第一个小于key的值A[j],将A[j]和A[i]的值交换;
4)从i开始向后搜索,即由前开始向后搜索(i++),找到第一个大于key的A[i],将A[i]和A[j]的值交换;
5)重复第3、4步,直到i=j; (3,4步中,没找到符合条件的值,即3中A[j]不小于key,4中A[i]不大于key的时候改变j、i的值,使得j=j-1,i=i+1,直至找到为止。找到符合条件的值,进行交换的时候i, j指针位置不变。另外,i==j这一过程一定正好是i+或j-完成的时候,此时令循环结束)。

实例

#include<iostream>
using namespace std;
void sort(int s[],int left,int right)//进行排序
{
    if(left<right)//判断取的key两边的数组下标是否符合排序规则
    {
        int i=left,j=right;
        int key=s[left];
        while(i<j)
        {
            while(i<j&&key<=s[j])//寻找数组小于key的下标(从右到左)
                j--;
            s[i]=s[j];
            while(i<j&&key>=s[i])//寻找数组大于key的下标(从左到右)
                i++;
            s[j]=s[i];
        }
        s[i] = key;
        sort(s,left,i-1);//递归子表1,在key的左边的下标
        sort(s,i+1,right);//递归子表2,在key的右边的下标
    }
}
void out(int s[])//输出数组
{
    int i;
    for(i=0;i<10;i++)
        cout<<s[i]<<" ";
        cout<<endl;
}
void main()
{
    int s[10]={1,9,8,7,6,5,4,3,2,1};
    out(s);
    sort(s,0,9);
    out(s);
}

添加新评论

已有 5 条评论

其实这些二级是不考的

熟悉的快排,熟悉的味道

反正自己也在一直看C语言,虽然自己本专业不是,作为一种爱好看到不懂的就想去钻研一下。

学点算法还是极好的

半叶子 半叶子 回复 @心灵博客
0 0

自己挺有兴趣的就一直看看 ,基础的看的都挺难的。