目录

一、排序的概念以及应用

二、常见排序算法的实现

1.插入排序

1.1直接插入排序

b.实现直接插入排序

1.2希尔排序（缩小增量排序）

2.选择排序

2.1直接选择排序

2.2堆排序

3.交换排序

3.1冒泡排序

一、排序的概念以及应用

1.排序的概念

        所谓排序，就是使一串记录，按照其中的某个或某个关键字的大小，递增或者递减的排列起来的操作。

        排序的稳定性：假定在待排序的记录序列中，存在多个具有相同关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中,r[i] = r[j],且r[i]在r[j]之前，在排序后的序列中,r[i]仍在r[j]之前，则这种排序算法是稳定的，否则称为不稳定的

        内部排序：数据元素全部放在内存中的排序

        外部排序：数据元素太多不能同时放在内存中，根据排序过程的要求不能再内外存之间移动数据的排序

二、常见排序算法的实现

        常见的排序算法包括：插入排序（直接插入排序，希尔排序），选择排序（选择排序，堆排序），交换排序（冒泡排序，快速排序），归并排序

1.插入排序

插入排序的基本思想是：把待排序的记录按其关键值的大小逐个插入到一个已经排好序的有序序列中，直到所有的记录插入完为止，得到一个新的有序序列。

1.1直接插入排序

        当插入第i（i>=1)个元素时，前面的array[0],array[1],...array[i-1]已经排好顺序，此时用array[i]的排序码与array[i-1],array[i-2],...的排序码进行比较，找到插入位置将array[i]插入，原来位置上的元素顺序后移。 a.先看插入一个数的情况，假设前面序列有序，为 1 3 5 6 如果插入7 则放在最后一个位置，如果插入2，则找到比2小的那个数，放在这个数的后面，如果插入 0，找到1仍旧比0大，则0放在最开始的位置，实现代码如下：

void InsertSort1(int * a,int n)
{
    int end = n-1;
    int tmp ;
    a[end+1] = tmp;
    while(end>=0)
    {
        if(tmp <a[end])
        {
            //往后挪动    
            a[end+1] = a[end];
            --end;
        }
        else
        {
            break;
        }
   }
    a[end+1] = tmp;

b.实现直接插入排序

        假设有一组序列： 9 1 2 5 7 4 8 6 3 5 ,将这个序列按照从小到大的顺序进行排序，思想是：先前两个数进行排序，end的位置在9,tmp为1,tmp<end，a[end]向后挪动，插入这个tmp，第二次，排序 则为1 9 2，end的位置在9,tmp的位置在2，进行排序，插入交换位置，第三次 1 2 9 5 依次类推，直到end的位置到3，5为tmp，遍历完整个序列结束排序。

        上述这个过程end的位置在不断变化，给一个变量，控制end的位置。可以使用for循环，end从0开始，到n-1。实现代码如下

void InsertSort(int * a, int n)
{
    for(int i = 0; i< ; i++)
    {
        int end = i;
        int tmp = a[end+1];
        while(end >= 0)
        {
            if(a[end] > tmp)
            {
                a[end+1] = a[end];
                --end;
            }
           else
            {
                break;
            }
        }
        a[end+1] = tmp;
    }
}

1.2希尔排序（缩小增量排序）

        希尔排序，又称缩小增量排序，希尔排序的基本思想是：先选定一个整数，把待排序文件中的所有分组，所有距离相同的记到同一个分组中，并对每一组内的记录进行排序，然后重复分组和排序的工作，当gap = 1的时候，所有的为有序。

      假设现在有一组数据： 9 8  7 6 5 4 3 2 1 ，先进行分组，gap = 3的为一组 （9，6，3；8，5，2；7，4，1）然后对每一组进行插入排序，end的位置在9，tmp为6，排序完6 9 3 这个时候end不再--，而是end-gap，实现这一步骤的代码如下：

int gap = 3;
int end;
int tmp = a[end+gap];
while(end >= 0)
{
    if(tmp<a[end])
    {
        a[end+gap] = a[end];
        end -= gap;
    }
    else
    {
        break;
    }
 }
  
a[end+gap] = tmp;

        上述过程只实现了一步的预排序和插入，想要对一组进行排序，end的位置需要变化，每次变化是有规律的，第一次end 在起始位置，第二次end在下标为3的位置，第三次end在下标为6的位置，一共有9个数，第一次变量i= 0,第三次i = n-gap，每次i++gap次，实现代码如下：

int gap = 3;
for(int i = 0;i<n-gap;i+=gap)
{
    int end = i;
    int tmp = a[end+gap];
    while(end>=0)
    {
        if(tmp>a[end])
        {
            a[end+gap] = a[end];
            end-=gap;
        }
        else
        {
            break;
        }
        
    }
    a[end+gap] = tmp;
}

上述过程实现了对一组数据进行排序，如果想要对所有组进行排序，需要对i进行改变，进而改变end的位置，由上述分组可以看出，gap为3的时候，分为了3组，i的起始位置分别为9 8 7，所以使用一个变量j,来控制i的变化，i= 0时，排序第一组，i=1的时候，排序第二组，i=3的时候排序第3组；实现代码如下：

int gap = 3;
for(int j = 0;j<gap;++j)
{
    for(int i = j; i<n-gap;i+=gap)
    {
        int end = i;
        int tmp = a[end+gap];
        while(end>=0)
        {
            if(tmp<a[end])
            {
                a[end+gap] = a[end];
                end -=gap;
            }
            else
            {
            break;
            }
         }
        a[end+gap] = tmp;
    }
}

//如果不想一组一组排，gap并排可以修改上述条件
for(int i = 0;i<n-gap;++i)

        排序的时候gap越大，大的数可以更快到后面，小的可以更快到前面，表面这个时候序列越不接近有序，gao越小，数据跳动越慢，越接近有序

        实际上的gap值是变化的，实现代码如下：

void ShellSort(int * a,int n)
{
    //gap>1 预排序
    // gap ==1 直接插入排序
    int gap = n;
    while(gap > 1)
    {
        gap = gap / 3 +1  //这里是为了保证最后一个数可以实现直接插入排序
        for(int i = 0; i<n-gap; ++i)
        {
            int end = i;
            int tmp = a[end+gap];
            while(end >= 0)
            {
                if(tmp <a[end])
                {
                    a[end+gap] = a[end];
                    end -= gap;
                }
                else
                {
                    break;
                }
        }

            a[end+gap] = tmp;
        }
}

2.选择排序

        基本思想：每次从待排序的数据元素中选出最小（或者最大）的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完

2.1直接选择排序

        在元素集合array[i]--array[n-1]中选择关键最大（小）的数据元素，如果它不是这组元素中的第一个（最后一个）元素，则将它与这组元素中的最后一个（第一个）进行交换，在剩余的array[i]--array[n-2]集合，重复上述步骤，直到集合剩余1个元素

        在这里改进一下直接选择排序，每次找到最大的和最小的，分别放在前面和后面。注意这里，如果maxi和begin指向了同一块，需要进行特殊处理，实现代码如下：

实现代码如下：

void SelectSort(int * a, int n)
{

    int begin = 0 , end = n-1;
    while(begin < end)
    {
        int mini = begin, maxi = begin;
        for(int i = begin +1; i<=end ; ++i)
        {
            if(a[i] <a[mini])
            {
                mini = i;
            }
        
            if(a[i] > a[maxi])
            {
                maxi = i;
            }
        
        }
        
        Swap(&a[begin],&a[mini]);
        //这里为了防止maxi和begin指向同一块位置
        if(maxi == begin)
        {
            maxi = mini;
        }
        Swap(&a[end],&a[maxi])
        ++begin;
    }
}

2.2堆排序

        思想:如果要排序一个升序，建立一个小堆，先将堆顶元素和最后一个元素交换，然后向下调整。如果要排序一个降序，建立一个大堆，将堆顶元素和最后一个元素交换，然后向下调整。

void AdjustDown(int * a, int n,int root)
{
    int parent = root;
    int child = 2*parent +1;
    
    while(child < n)
    {
        if(child+1 <n && a[child+1] >a[child])
        {
            ++child;
        }

        //小的向下调整 建立大堆
    
        if(a[parent] <a[child])
        {
            Swap(&a[parent],&a[child]);
            parent = child;
            child = 2*parent +1;
        }
       
        else
        {
            break;
        }
        


}
//要排一个升序，升序建立一个大堆 
//这里形参是一个数组，从数组开始要对一个数进行排序，先找最后一个非叶子节点建立大堆，堆顶是最大的数
//然后找到最后一个数，此时大堆的最后一个数是较小的数，放在堆顶，再去调整为大堆，此时第二大的数就在堆顶
void HeapSort(int * a, int n)
{
    //从倒数第一个非叶子节点开始建立大堆
    for(int i = n-1-1/2; i>=0;i--)
    {
        AdjustDown(a,n,i);
    }

    int end = n-1;
    while(end >0)
    {
        Swap(&a[0],&a[end]);  //将堆顶元素和最后一个元素交换
        AdjustDown(a,end,0);  //然后将堆顶元素向下调整
        end--;
    }
}

}

3.交换排序

        交换排序的基本思想：所谓交换，就是根据序列中两个记录键值的比较结果来对换之两个记录在序列中的位置，交换排序的特点是：将键值较大的记录向序列的尾部移动，键值较小的记录向序列的前部移动

3.1冒泡排序

        冒泡排序的思想就是：a[i]和a[i+1]进行比较，大的往后挪动，一直重复这个过程，这是单趟的冒泡排序，多趟就是控制i的变化，每次冒泡都会把这轮中最大的数放在最后面，可以使用一个变量j,i第一次到最后一个值，第二次到倒数第二个，...i的变化就是0--n-j;j++。实现代码如下:

void BubbleSort(int * a, int n)
{
    for(int j = 0; j<n;j++)
    {
        for(int i = 0; i<n-j;i++)
        {
            if(a[i] >a[i+1])
            {
                Swap(&a[i],&a[i+1]);
            }
        }
    }
}