排序算法——交换排序-蒲公英云

排序算法——交换排序

冒泡排序：

转载：冒泡排序（百度百科）

冒泡排序（Bubble Sort），是一种计算机科学领域的较简单的排序算法。

它重复地走访过要排序的元素列，依次比较两个相邻的元素，如果他们的顺序（如从大到小、首字母从A到Z）错误就把他们交换过来。走访元素的工作是重复地进行直到没有相邻元素需要交换，也就是说该元素已经排序完成。

这个算法的名字由来是因为越大的元素会经由交换慢慢“浮”到数列的顶端（升序或降序排列），就如同碳酸饮料中二氧化碳的气泡最终会上浮到顶端一样，故名“冒泡排序”。

冒泡排序算法的原理如下：

比较相邻的元素。如果第一个比第二个大，就交换他们两个。
对每一对相邻元素做同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。
针对所有的元素重复以上的步骤，除了最后一个。
持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

代码：

/冒泡排序
//冒泡：Bubble 
#include<iostream>
#include<algorithm>
using namespace std;
void Bubble(int *a,int n)
{
    int i,j;
    for(j=0;j<n-1;j++)
        for(i=0;i<n-1;i++)
        {
            if(a[i]>a[i+1])
                swap(a[i],a[i+1]);
        }
}
int main()
{
    int a[]={1,5,3,9,7,4,3,8};
    int n=sizeof(a)/sizeof(int);
    Bubble(a,n); 
    for(int i=0;i<n;i++)
        cout<<a[i]<<" ";
    return 0; 
}

快速排序：

转载：白话经典算法系列之六快速排序快速搞定

快速排序是C.R.A.Hoare于1962年提出的一种划分交换排序。它采用了一种分治的策略，通常称其为分治法(Divide-and-ConquerMethod)。

该方法的基本思想是：

1．先从数列中取出一个数作为基准数。

2．分区过程，将比这个数大的数全放到它的右边，小于或等于它的数全放到它的左边。

3．再对左右区间重复第二步，直到各区间只有一个数。

虽然快速排序称为分治法，但分治法这三个字显然无法很好的概括快速排序的全部步骤。因此我的对快速排序作了进一步的说明：挖坑填数+分治法：

先来看实例吧，定义下面再给出（最好能用自己的话来总结定义，这样对实现代码会有帮助）。

以一个数组作为示例，取区间第一个数为基准数。

初始时，i = 0; j = 9; X = a[i] = 72

由于已经将a[0]中的数保存到X中，可以理解成在数组a[0]上挖了个坑，可以将其它数据填充到这来。

从j开始向前找一个比X小或等于X的数。当j=8，符合条件，将a[8]挖出再填到上一个坑a[0]中。a[0]=a[8]; i++; 这样一个坑a[0]就被搞定了，但又形成了一个新坑a[8]，这怎么办了？简单，再找数字来填a[8]这个坑。这次从i开始向后找一个大于X的数，当i=3，符合条件，将a[3]挖出再填到上一个坑中a[8]=a[3]; j—;

数组变为：
70 1

i = 3; j = 7; X=72

再重复上面的步骤，先从后向前找，再从前向后找。

从j开始向前找，当j=5，符合条件，将a[5]挖出填到上一个坑中，a[3] = a[5]; i++;

从i开始向后找，当i=5时，由于i==j退出。

此时，i = j = 5，而a[5]刚好又是上次挖的坑，因此将X填入a[5]。

数组变为：
70 2

可以看出a[5]前面的数字都小于它，a[5]后面的数字都大于它。因此再对a[0…4]和a[6…9]这二个子区间重复上述步骤就可以了。

对挖坑填数进行总结

1．i =L; j = R; 将基准数挖出形成第一个坑a[i]。

2．j—由后向前找比它小的数，找到后挖出此数填前一个坑a[i]中。

3．i++由前向后找比它大的数，找到后也挖出此数填到前一个坑a[j]中。

4．再重复执行2，3二步，直到i==j，将基准数填入a[i]中。

照着这个总结很容易实现挖坑填数的代码：

//快速排序
#include<stdio.h>
void quick_sort(int a[],int l,int r)
{
    if(l<r)
    {
        int i=l;
        int j=r;
        int tmp=a[i];
        while(i<j)
        {
            while(i<j&&a[j]>=tmp)
                j--;
            if(i<j)
            {
                a[i]=a[j];
                i++;
            }
            while(i<j&&a[i]<=tmp)
                i++;
            if(i<j)
            {
                a[j]=a[i];
                j--;
            }
        }
        a[i]=tmp;//当i=j时，退出循环
        quick_sort(a,l,i-1);
        quick_sort(a,i+1,r); 
    }
}
int main()
{
    int a[]={1,5,3,7,6,9,2,7,4,5};
    int n=sizeof(a)/sizeof(int);
    quick_sort(a,0,n-1);
    for(int i=0;i<n;i++)
        printf("%d ",a[i]);
    return 0;
}