一.冒泡排序(Bubble Sort)

基本思想:两两比较相邻记录的关键字,如果反序则交换,直到没有反序的记录为止。

//冒泡排序
void BubbleSort(int *p, int length)
{
    for (int i = 0; i < length-1; i++)
    {
        for (int j =length-1; j>=i;j--)
        {
            if (p[j-1] > p[j])
            {
                swap(p[j-1], p[j]);
            }
        }
    }
}

排序前的顺序为:9 1 5 8 3 7 4 6 2

当i=1时,交换的情况如下:

 

二.简单选择排序(Simple Selection Sort)

通过n-1次关键字间的比较,从n-i+1个记录中选择最小的记录,并和第i次(1≤i≤n)记录交换

//简单选择排序
void SimSelSort(int *p, int length)
{
    int i, j, min;
    for (i = 0; i < length - 1; i++)
    {
        min = i;                       //记录最小值的下标,初始化为i
        for (j=i+1;j<=length-1;j++)
        {
            if (p[j] < p[min])
                min = j;            //通过不断地比较,得到最小值的下标
        }
        swap(p[i], p[min]);
    }
}

三.直接插入排序

把一个记录直接插入到已经排好序的有序表中,从而得到一个新的,记录数增1的有序表。

//直接插入排序
void StrInserSort(int *p, int length)
{
    int i, j;
    for (i =1; i <length; i++)
    {
        if ( p[i]<p[i-1])
        {
          int tmp;
          tmp = p[i];
          for (j = i - 1; p[j] > tmp; j--)
             p[j+1] = p[j];
          p[j+1] = tmp;
        }
    }
}
 

四.希尔排序(Shell Sort)

    希尔排序是把记录按下标的一定增量分组,对每组使用直接插入排序算法排序;随着增量逐渐减少,每组包含的关键词越来越多,当增量减至1时,整个文件恰被分成一组,算法便终止。

 

void ShellSort(int *p, int length)
{
    int i, j;
    int increment = length;
    do {
         increment = increment / 3 +1;
         for (i = increment ; i <= length - 1; i++)
        {
              if (p[i] < p[i - increment])
              {
                int tmp;
                tmp = p[i];
                for (j = i - increment; j >= 0 && tmp < p[j]; j -= increment)
                  p[j + increment] = p[j];
                p[j + increment] = tmp;
              }
            }
    } while (increment > 1);
}

五.堆排序(Heap Sort)

1.堆的定义

   堆是具有下列性质的完全二叉树:每个结点的值都大于或等于其左右孩子结点的值,称为大顶堆;或者每个结点的值都小于或等于其左右孩子结点的值,称为小顶堆。

2.堆排序

堆排序的基本思想(利用堆,如大顶堆进行排序):将待排序的序列构造成一个大顶堆。此时,整个序列的最大值就是堆顶的根结点。将它移走(其实就是将它与堆数组的末尾元素交换,此时末尾元素就是最大值),然后将剩余n-1个序列重新构造成一个堆,这样就会得到n个元素的次小值。如此反复执行,便能得到一个有序序列。

 

主要问题:

1.如何由一个无序序列构建成一个堆?

2.如何在输出堆顶元素后,调整剩余元素成为一个新的堆?

//构造最大堆
void MaxHeapFixDown(int *p, int i, int length) {
    int j = 2 * i + 1;
    int temp = p[i];
    while (j<length) {
        if (j + 1<length && p[j]<p[j + 1])
            ++j;
        if (temp>p[j])
            break;
        else {
            p[i] = p[j];
            i = j;
            j = 2 * i + 1;
        }
    }
    p[i] = temp;
}

//堆排序
void HeapSort(int *p, int length) {
    for (int i = length / 2 - 1; i >= 0; i--)
    {
        MaxHeapFixDown(p, i, length);
    }
    for (int i = length - 1; i >= 1; i--)
    {
        swap(p[i], p[0]);
        MaxHeapFixDown(p, 0, i);
        cout << "i的值:" << i << " 排序:";
        ergodic(p, 9);
    }
}

六.归并排序(Merging Sort)

  归并排序就是利用归并思想实现的排序方法。原理:假设初始序列含有n个记录,则可以看成是n个有序的子序列,每个子序列长度为1,然后再两两归并,得到[n/2]个长度为2或1的有序子序列;再两两归并….,如此重复,直到的一个长度为n的有序序列为止,称为2路归并排序。

七.快速排序(Quick Sort)

    快速排序的基本思想是:通过一趟排序将待排记录分割成独立的两部分,其中一部分记录的关键字均比另外一部分记录的关键字小,则可分别对这两部分记录继续进行排序,以达到整个序列有序的目的。

//快速排序
void QuickSort(int *p, int l, int r)
{
    if (l< r)
    {
        int i = l, j = r, x = p[l];
        while (i < j)
        {
            while (i < j && p[j] >= x) // 从右向左找第一个小于x的数 
                j--;
            if (i < j)
                p[i++] = p[j];
            while (i < j && p[i]< x) // 从左向右找第一个大于等于x的数 
                i++;
            if (i < j)
                p[j--] = p[i];
        }
        p[i] = x;
        QuickSort(p, l, i - 1); // 递归调用 
        QuickSort(p, i + 1, r);  
    }
}

 总结

 

参考:《大话数据结构》