排序算法详解（二）

前面说了排序算法中的插入排序，下面就来看下排序中的快速排序。

在快速排序中，最简单的就是大家耳熟能详的冒泡排序，那么到底什么是冒泡排序呢？冒泡排序的思想就是：首先将第一个元素与第二个元素进行比较，若未逆序，则将两个元素的位置进行交换，然后继续比较第二个和第三个元素之间的大小，依此类推，知道第n-1个元素和第n个元素比较完成了以后，第一趟冒泡排序就终止了，它将最大的元素安置到了序列的最后，然后在进行第二趟冒泡排序，对前n-1个元素进行冒泡排序，然后将最大值放入n-1的位置上，以此类推，逐趟进行序列的遍历，而整个排序过程的结束就是在一趟排序中，没有元素进行交换。

下面就是一个使用冒泡排序的一个小例子：

[cpp]
#include<stdio.h>
#include<stdlib.h>

#define N 100
int L[N];

void Bubblesort(int n)
{
    int i,j,t;
    for(i=0;i<n;i++)
    {
        for(j=i;j<=n;j++)
        {
            if(L[j]>L[j+1])
            {   t = L[j+1];
                L[j+1] = L[j];
                L[j] = t;
                continue;
            }
        }
        break;
    }
    for(i=0;i<=n;i++)
        printf("L[%d]=%d\n",i,L[i]);
}

int main()
{
    int i,n;
    scanf("%d",&n);
    for(i=0;i<=n;i++)
        scanf("%d",&L[i]);
    Bubblesort(n);
    return 0;
}
由上面可以明显的看出，冒泡排序的时间复杂度是O(n2)。其是稳定的排序。
在快速排序中，冒泡排序是最简单的一种排序，而快速排序是对冒泡排序的一种改进，其算法的基本思想是：通过一趟排序将序列分割成独立的两部分，其中一部分的元素比另一部分的元素小，然后将这两部分序列再进行快速排序排序，以最终达到整个序列有序。快速排序比前面的冒泡排序理解起来稍微有点难度，下面看这个例子，以供大家深入的理解一下：

[cpp]
#include<stdio.h>
#include<stdlib.h>

#define N 100

void Quicksort(int *arr,int StartPos,int EndPos)
{
    int i,j,key;
    key = arr[StartPos];
    i = StartPos;
    j = EndPos;
    while(i<j)
    {
        while(arr[j]>=key && i<j)
            j--;
        arr[i] = arr[j];
        while(arr[i]<=key && i<j)
            i++;
        arr[j] = arr[i];
    }
    arr[i] = key;
    if(i-1>StartPos)
        Quicksort(arr,StartPos,i-1);
    if(EndPos>i+1)
        Quicksort(arr,i+1,EndPos);
}

void Print(int *arr,int EndPos)
{
    int i;
    for(i=0;i<=EndPos;i++)
        printf("L[%d]=%d\n",i,arr[i]);
}

int main()
{
    int i,n,L[N];
    scanf("%d",&n);
    for(i=0;i<n;i++)
        scanf("%d",&L[i]);
    Quicksort(L,0,n-1);
    Print(L,n-1);
}
上面采用了递归的方法来进行快速排序。快速排序是不稳定的。
这部分主要讲解的是快速排序，下面还将继续进行其余排序方法的说明。

作者：wanchres

补充：软件开发 , C++ ,