// Sort.cpp : 定义控制台应用程序的入口点。//#include "stdafx.h"#include <stdlib.h>/************************************************************************//* copyright (c) 2014 kernel_main/* c++面试常考点/* 转载请注明出处：http://www.cnblogs.com/kernel0815//************************************************************************///交换两个数void swap(int &a, int &b){    int tmp = a;    a = b;    b = tmp;}#define PrintList(list, count) do\{    for (int i=0;i<count;i++)    {        printf("%d ", list[i]);    }        printf("\r\n");}while(0);//1. 冒泡排序/*算法原理:冒泡排序算法的运作如下：（从后往前）比较相邻的元素。如果第一个比第二个大，就交换他们两个。对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。针对所有的元素重复以上的步骤，除了最后一个。持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。*/void BubbleSort(int* list, int count){    printf("===[%s]==\n", __FUNCTION__);    PrintList(list, count);    for (int i=0; i<count-1; i++)    {        for (int j=count-1; j>i; j--)        {            if (list[j-1] > list[j])            {                swap(list[j-1], list[j]);            }        }        PrintList(list, count);    }}//2. 选择排序/*对比数组中前一个元素跟后一个元素的大小，如果后面的元素比前面的元素小则用一个变量k来记住他的位置，接着第二次比较，前面“后一个元素”现变成了“前一个元素”，继续跟他的“后一个元素进行比较如果后面的元素比他要小则用变量k记住它在数组中的位置(下标)，等到循环结束的时候，我们应该找到了最小的那个数的下标了，然后进行判断，如果这个元素的下标不是第一个元素的下标，就让第一个元素跟他交换一下值，这样就找到整个数组中最小的数了。然后找到数组中第二小的数，让他跟数组中第二个元素交换一下值，以此类推。*/void SelectSort(int* list, int count){    printf("===[%s]==\n", __FUNCTION__);    PrintList(list, count);    int i, j, min_index, tmp;    for (i=0; i<count-1; i++)    {        tmp = list[i];        min_index = i;        for (j=i+1; j<count; j++)        {            if (list[j] < tmp)            {                tmp = list[j];                min_index = j;            }        }        if (min_index != i)        {            swap(list[i], list[min_index]);        }        PrintList(list, count);    }}//3. 插入排序/*⒈ 从第一个元素开始，该元素可以认为已经被排序⒉ 取出下一个元素，在已经排序的元素序列中从后向前扫描⒊ 如果该元素（已排序）大于新元素，将该元素移到下一位置⒋ 重复步骤3，直到找到已排序的元素小于或者等于新元素的位置⒌ 将新元素插入到下一位置中⒍ 重复步骤2~5如果比较操作的代价比交换操作大的话，可以采用二分查找法来减少比较操作的数目。该算法可以认为是插入排序的一个变种，称为二分查找排序。*/void InsertSort(int* list, int count){    printf("===[%s]==\n", __FUNCTION__);    PrintList(list, count);    int i, j, tmp;    for (i=1; i<count; i++)    {        if (list[i-1] > list[i])        {            tmp = list[i];            for (j=i-1; j>=0 && list[j] > tmp; j--)            {                list[j+1] = list[j];            }            list[j+1] = tmp;        }        PrintList(list, count);    }}//4. 快速排序/*1）设置两个变量i、j，排序开始的时候：i=0，j=N-1；2）以第一个数组元素作为关键数据，赋值给key，即key=A[0]；3）从j开始向前搜索，即由后开始向前搜索(j--)，找到第一个小于key的值A[j]，将A[j]和A[i]互换；4）从i开始向后搜索，即由前开始向后搜索(i++)，找到第一个大于key的A[i]，将A[i]和A[j]互换；5）重复第3、4步，直到i=j；   (3,4步中，没找到符合条件的值，即3中A[j]不小于key,4中A[i]不大于key的时候改变j、i的值，  使得j=j-1，i=i+1，直至找到为止。找到符合条件的值，进行交换的时候i， j指针位置不变。  另外，i==j这一过程一定正好是i+或j-完成的时候，此时令循环结束）。*/int PartSort(int* list, int lowIndex, int highIndex){    int tmp = list[lowIndex];    while(lowIndex < highIndex)    {        while(lowIndex < highIndex && list[highIndex] >= tmp)        {            highIndex--;        }        swap(list[lowIndex], list[highIndex]);        while(lowIndex < highIndex && list[lowIndex] <= tmp)        {            lowIndex++;        }        swap(list[lowIndex],list[highIndex]);    }    PrintList(list, 10);    return lowIndex;}void QSort(int *list, int lowIndex, int highIndex){    int tmpIndex = 0;    if (lowIndex < highIndex)    {        tmpIndex = PartSort(list,lowIndex, highIndex);        QSort(list, lowIndex, tmpIndex-1);        QSort(list, tmpIndex+1, highIndex);    }    }void QuickSort(int* list, int count){    printf("===[%s]==\n", __FUNCTION__);    PrintList(list, 10);    QSort(list, 0, count-1);}//5. 堆排序/*堆排序利用了大根堆（或小根堆）堆顶记录的关键字最大（或最小）这一特征，使得在当前无序区中选取最大（或最小）关键字的记录变得简单。（1）用大根堆排序的基本思想① 先将初始文件R[1..n]建成一个大根堆，此堆为初始的无序区② 再将关键字最大的记录R[1]（即堆顶）和无序区的最后一个记录R[n]交换，由此得到新的无序区R[1..n-1]和有序区R[n]，且满足R[1..n-1].keys≤R[n].key③由于交换后新的根R[1]可能违反堆性质，故应将当前无序区R[1..n-1]调整为堆。然后再次将R[1..n-1]中关键字最大的记录R[1]和该区间的最后一个记录R[n-1]交换，由此得到新的无序区R[1..n-2]和有序区R[n-1..n]，且仍满足关系R[1..n-2].keys≤R[n-1..n].keys，同样要将R[1..n-2]调整为堆。……直到无序区只有一个元素为止。（2）大根堆排序算法的基本操作：① 初始化操作：将R[1..n]构造为初始堆；② 每一趟排序的基本操作：将当前无序区的堆顶记录R[1]和该区间的最后一个记录交换，然后将新的无序区调整为堆（亦称重建堆）。注意①只需做n-1趟排序，选出较大的n-1个关键字即可以使得文件递增有序。②用小根堆排序与利用大根堆类似，只不过其排序结果是递减有序的。堆排序和直接选择排序相反：在任何时刻堆排序中无序区总是在有序区之前，且有序区是在原向量的尾部由后往前逐步扩大至整个向量为止特点堆排序（HeapSort）是一树形选择排序。堆排序的特点是：在排序过程中，将R[l..n]看成是一棵完全二叉树的顺序存储结构，利用完全二叉树中双亲结点和孩子结点之间的内在关系（参见二叉树的顺序存储结构），在当前无序区中选择关键字最大（或最小）的记录区别直接选择排序中，为了从R[1..n]中选出关键字最小的记录，必须进行n-1次比较，然后在R[2..n]中选出关键字最小的记录，又需要做n-2次比较。事实上，后面的n-2次比较中，有许多比较可能在前面的n-1次比较中已经做过，但由于前一趟排序时未保留这些比较结果，所以后一趟排序时又重复执行了这些比较操作。堆排序可通过树形结构保存部分比较结果，可减少比较次数。*/void HeapAdjust(int* list, int s, int m){    int temp = list[s];    for(int j=2*s+1;j<=m;j = 2*j+1)    {        if(list[j]<list[j+1]&&j<m)        {            j++;        }        if(temp>list[j])            break;        list[s] = list[j];        s = j;    }    list[s] = temp;}void HeapSort(int* list, int count){    printf("===[%s]==\n", __FUNCTION__);    //创建一个大顶堆    for(int s = count/2-1;s>=0;s--)    {        HeapAdjust(list,s,count-1);    }    //排序    for(int i = count-1;i >= 1;i--)    {        swap(list[0],list[i]);        HeapAdjust(list,0,i-1);        PrintList(list, 10);    }}//6. shell排序/*希尔排序属于插入类排序,是将整个有序序列分割成若干小的子序列分别进行插入排序。排序过程：先取一个正整数d1<n，把所有序号相隔d1的数组元素放一组，组内进行直接插入排序；然后取d2<d1，重复上述分组和排序操作；直至di=1，即所有记录放进一个组中排序为止。*/void ShellSort(int* list, int count){    printf("===[%s]==\n", __FUNCTION__);    int i,j;    int temp;    int increment = count;    do    {        increment = increment/3+1;        for(i = increment;i<count;i++)        {            if(list[i]<list[i-increment])            {                temp = list[i];                for(j=i-increment;j>=0&&list[j]>temp;j-=increment)                {                    list[j+increment] = list[j];                }                list[j+increment] = temp;            }            PrintList(list, 10);        }    }while(increment>1);}//7. 归并排序/*归并操作的工作原理如下：第一步：申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列第二步：设定两个指针，最初位置分别为两个已经排序序列的起始位置第三步：比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置重复步骤3直到某一指针超出序列尾将另一序列剩下的所有元素直接复制到合并序列尾*///将有个有序数组排序void Merge(int *list,int start,int mid,int end){    const int len1 = mid -start +1;    const int len2 = end -mid;    const int len = end - start +1;    int i,j,k;    int * front = (int *)malloc(sizeof(int)*len1);    int * back = (int *)malloc(sizeof(int)*len2);    for(i=0;i<len1;i++)        front[i] = list[start+i];    for(j=0;j<len2;j++)        back[j] = list[mid+j+1];    for(i=0,j=0,k=start;i<len1&&j<len2&&k<end;k++)    {        if(front[i]<back[j])        {            list[k] = front[i];            i++;        }else        {            list[k] = back[j];            j++;        }    }        while(i<len1)    {        list[k++] = front[i++];    }    while(j<len2)    {        list[k++] = back[j++];    }}//归并排序void MSort(int *list,int start, int end){    if(start<end)    {        int mid = (start+end)/2;        MSort(list,0,mid);        MSort(list,mid+1,end);        Merge(list,start,mid,end);        PrintList(list, 10);    }}void MergeSort(int* list, int count){    printf("===[%s]==\n", __FUNCTION__);    MSort(list,0,count-1);}#define INT_ARR {3,5,9,2,7,6,1,8,0,4}int _tmain(int argc, _TCHAR* argv[]){    int list1[10] = INT_ARR;    int list2[10] = INT_ARR;    int list3[10] = INT_ARR;    int list4[10] = INT_ARR;    int list5[10] = INT_ARR;    int list6[10] = INT_ARR;    int list7[10] = INT_ARR;    BubbleSort(list1, 10);    SelectSort(list2, 10);    InsertSort(list3, 10);    QuickSort(list4, 10);    HeapSort(list5, 10);    ShellSort(list6, 10);    MergeSort(list7, 10);    return 0;}