内排序算法的整理

对各种内排序算法进行了整理，不足的日后补充。

1.冒泡排序

冒泡排序属于交换排序，其基本思想是通过无序区中相邻元素关键字间的比较和位置的交换使关键字最小的元素如气泡一般逐渐往上“漂浮”至“水面”，该算法时间复杂度为O(n^2)。

伪代码如下：

void BubbleSort(RecType R[],int n)
{
    int i,j;
    for(i=0;i<n-1;i++)
        for(j=n-1;j>i;j--)            //将R[i]元素归位 
            if(R[j].key<R[j-1].key) //相邻的两个元素反序时 
                swap(R[j],R[j-1]);  //将R[j]和R[j-1}两个元素交换 
}

C++代码如下：

 1 #include<iostream>
 2 using namespace std;
 3 
 4 void BubbleSort(int a[],int n)
 5 {
 6     int i,j;
 7     for(i=0;i<n-1;i++)
 8         for(j=n-1;j>i;j--)
 9             if(a[j]<a[j-1])
10             {
11                 int c;
12                 c=a[j-1];
13                 a[j-1]=a[j];
14                 a[j]=c;
15             }
16     
17 }
18 int main()
19 {
20     int i;
21     int a[10]={8,4,6,2,5,1,0,43,17,42};
22     BubbleSort(a,10);
23     for(i=0;i<10;i++)
24         cout<<a[i]<<endl;
25         
26     return 0;
27 }

运行结果：

2.梳排序

梳排序是冒泡排序的改进算法，算法思路是将冒泡排序中不需要进行元素交换的比较过程跳过。

伪代码如下：

void BubbleSort1(RecType R[],int n)
{
    int i,j;
    bool exchange;
    for(i=0;i<n-1;i++)
    {
        exchange=false;                    //一趟前exchange置为假 
        for(j=n-1;j>i;j--)                //归位R[i]，循环n-i-1次 
            if(R[j].key<R[j-1].key)        //相邻两个元素反序时 
            { 
                swap(R[j],R[j-1]);        //将R[j]和R[j-1}两个元素交换 
                exchange=true;            //一旦有交换，exchange置为真 
            }
        if(!exchange)                    //本趟没有发生交换，中途结束算法 
            return;
    }
}

C++代码如下：

 1 #include<iostream>
 2 using namespace std;
 3 
 4 void BubbleSort1(int a[],int n)
 5 {
 6     int i,j;
 7     bool exchange;
 8     for(i=0;i<n-1;i++)
 9     {
10         exchange=false;
11         for(j=n-1;j>i;j--)
12             if(a[j]<a[j-1])
13             {
14                 int c;
15                 c=a[j-1];
16                 a[j-1]=a[j];
17                 a[j]=c;
18                 exchange=true;
19             }
20         if(!exchange)
21             return;
22     }
23 }
24 int main()
25 {
26     int i;
27     int a[10]={8,4,6,2,5,1,0,43,17,42};
28     BubbleSort1(a,10);
29     for(i=0;i<10;i++)
30         cout<<a[i]<<endl;
31         
32     return 0;
33 }

运行结果：

3.快速排序

快速排序算法思路是在待排序的n个元素中任取一个元素作为基准，把该元素放入适当位置后，数据序列被此元素划分成两部分。所有关键字比该元素关键字小的元素放置在前一部分，所有比它大的元素放置在后一部分，并把该元素排在这两部分的中间，这个过程称为一趟快速排序，即一趟划分。

伪代码如下：

int partition(RecType R[],int s,int t)    //一趟划分 
{
    int i=s,j=t;
    RecType tmp=R[i];                    //以R[i]为基准 
    while(i<j)                            //从两端交替向中间扫描，直至i=j为止 
    {
        while(j>i && R[j].key>=tmp.key)
            j--;                        //从右向左扫描，找一个小于tmp.key的R[j] 
        R[i]=R[j];                        //找到这样的R[j]，放入R[i]处 
        while(i<j && R[i].key<=tmp.key)
            i++;                        //从左向右扫描，找一个大于tmp.key的R[i] 
        R[j]=R[i];                        //找到这样的R[i],放入R[j]处 
    }
    R[i]=tmp;
    return i;
}

void QuickSort(RecType R[],int s,int t) //对R[s..t]的元素进行快速排序 
{
    int i;
    if(s<t)                                //区间内至少存在两个元素的情况 
    {
        i=partition(R,s,t);
        QuickSort(R,s,i-1);                //对左区间递归排序 
        QuickSort(R,i+1,t);                //对右区间递归排序 
    }
}

C++代码如下：

 1 #include<iostream>
 2 using namespace std;
 3 
 4 int partition(int a[],int s,int t)
 5 {
 6     int i=s,j=t;
 7     int tmp=a[i];
 8     while(i<j)            
 9     {
10         while(j>i && a[j]>=tmp)
11             j--;                
12         a[i]=a[j];    
13         while(i<j && a[i]<=tmp)
14             i++;
15         a[j]=a[i];
16     }
17     a[i]=tmp;
18     return i;
19 }
20 
21 void QuickSort(int a[],int s,int t)
22 {
23     int i;
24     if(s<t)
25     {
26         i=partition(a,s,t);
27         QuickSort(a,s,i-1);
28         QuickSort(a,i+1,t);
29     }
30 }
31 
32 int main()
33 {
34     int i;
35     int a[10]={8,4,6,2,5,1,0,43,17,42};
36     QuickSort(a,0,9);
37     for(i=0;i<10;i++)
38         cout<<a[i]<<endl;
39         
40     return 0;
41 }

运行结果：