高级排序算法(Shell，快速)

Shell排序：

希尔排序是建立在减少增量排序的基础上的。

基本思想：
　　先取一个小于n的整数d1作为第一个增量，把文件的全部记录分成d1个组。所有距离为dl的倍数的记录放在同一个组中。先在各组内进行直接插入排序；然后，取第二个增量d2

#include<iostream>
using namespace std;
template <class T>
void ShellSort(T list[], int n)        //希尔排序,分组排序使用插入排序法

{
    register int hCnt;        //分组组数,也就是增量大小

    register int i,j,h;
    int increments[20];        //存放增量的数组

    int k;

    for(h=1,i=0; h<n; h=3*h+1,i++)        //保存增量,h=h*3+1是最好的增量选择

        increments[i] = h;

    for(i--; i>=0; i--)
    {
        h = increments[i];        //从大到小取出增量进行分组排序


        for(hCnt=h; hCnt<h*2; hCnt++)        //一共有hCnt个分组，所以每趟排hCnt次

        {
            j = hCnt;            //从每组的第二个元素开始，因为插入排序默认第一个元素有序

            while(j < n)
            {
                T tmp = list[j];        //小的元素前移，这里j标示的是此趟排序要插入的元素，在该组里它左边的元素为有序

                k = j;            //保存下标

                while((k >= h) && (tmp < list[k-h]))
                {
                    list[k] = list[k-h];        //大的元素后移

                    k-=h;
                }
                list[k] = tmp;        //找到插入点

                j+=h;
            }
        }
    }
}

void main()
{
    int list[10]={10,5,6,9,8,1,7,3,2,4};
    ShellSort(list,10);
    cout<<"排序后得到：";
    for(int i=0; i<10; i++)
        cout<<list[i]<<' ';
    cout<<endl;
}

 

快速排序：

快速排序是目前实际应用中最快的排序方法了，这里引用在网上看到的一个网友blog里记载的快速排序详细过程，觉得很不错，借过来用用。
原文地址：http://blog.donews.com/sowen/articles/204230.aspx

本文将介绍一种另类的快速排序（其实也不是什么新方法，估计也有不少朋友见过了）。一般的quicksort如果不是同时从左和从右找，发现前值小于后值就交换，然后递归继续；就是先假定一个位置的元素为pivot，然后不同方向搜索。这些方法都需要循环几次，所以一般在网上看到的代码都有用到几个while，然后再递归两次。下面你将看到一个quicksort只用了一次while。

快速排序原理是使用分区法，比如以下这个数组

[60, 30, 80, 70, 50, 20]

先假定 60 是pivot，选择它下一个值，我们称为smallend，稍后我们再解释它的意思。

根据以上所述，pivot的index在0，该值为60；smallend的index在1，该值为30。

然后我们从smallend开始往前，我们把往前的那个指针称为idx，现在idx为1，因为我们是从smallend的位置开始往前的。只有发生以下三种情况：

1．当我们发现一个比pivot大的值，什么野不做。

2． 当我们发现一个比pivot小的值，把它和smallend位置的那个元素交换，并让smallend++

3．Smallend = idx，不交换，但是让smallend++

比如上面那个数组，idx=1，元素为30，因为<60，但是发现这个位置就是smallend了，于是直接加1，现在数组个元素位置不变，smallend=2。

接下来idx=2，元素为80，因为 >60，什么也不做，继续往前；idx=3，元素为70，什么也不做。Idx=4，元素为50，把它和smallend位置的元素交换，并增加smallend，数组变成

[60, 30, 50, 70, 80, 20]

现在smallend为3，idx为4。

继续往前走，idx=5，元素为20，交换，增加smallend。数组变为

[60, 30, 50, 20, 80, 70]

循环已经结束。Smallend=4，也就是正指向元素80那个位置。

相信大家现在大概直到，smallend就是指所有比pivot小的元素在数组中后面那个位置。

现在，我们把smallend减1，smallend=3，指向元素20的位置。我们把这个元素和pivot交换。那么pivot已经找到它的位置了——它左边的所有值都比自己小，右边所有值都比自己大。数组已经变成

[20, 30, 50, 60, 80, 70]

然后，再开始递归，quicksort（左边），quicksort（右边）。结束！

（该程序实例里，边界值是默认为数组first元素）

#include<iostream>
using namespace std;

template <class T>
void Swap(T list[], int index1, int index2)
{
    if(index1 == index2)
        return;
    T tmp = list[index1];
    list[index1] = list[index2];
    list[index2] = tmp;
}

template <class T>
void QuickSort(T list[], int first, int last)        //快速排序

{
    if (first < last)
    {
        int smallend = first+1;        //smallend实际是指向右边(大序数组)的最左元素

        int index = first+1;        //从第一个元素(边界值)的右边一个元素开始

        
        while (index <= last)
        {
            if (list[index] < list[first])
            {
                Swap(list, index, smallend);
                smallend++;
            }
            index++;
        }
        
        Swap(list, first, smallend-1);        //将边界值插到边界上,这时数组分两块

        QuickSort(list, first, smallend-1);
        QuickSort(list, smallend, last);
    }
}

void main()
{
    int list[10] = {10,5,6,9,8,1,7,3,2,4};
    QuickSort(list, 0, 9);
    cout<<"排序后得到：";
    for(int i=0; i<10; i++)
        cout<<list[i]<<' ';
    cout<<endl;
}