数据结构中各种排序的思路

排序算法中的稳定和不稳定指的是什么？
若在待排序的纪录中，存在两个或两个以上的关键码值相等的纪录，经排序后这些记录的相对次序仍然保持不变，则称相应的排序方法是稳定的方法，否则是不稳定的方法。

内部排序和外部排序
根据排序过程中涉及的存储器不同，可以讲排序方法分为两大类：一类是内部排序，指的是待排序的几率存放在计算机随机存储器中进行的排序过程；另一类的外部排序，指的是排序中要对外存储器进行访问的排序过程。
内部排序是排序的基础，在内部排序中，根据排序过程中所依据的原则可以将它们分为5类：插入排序、交换排序、选择排序、归并排序和基数排序；
根据排序过程的时间复杂度来分，可以分为三类：简单排序、先进排序、基数排序。
评价排序算法优劣的标准主要是两条：一是算法的运算量，这主要是通过记录的比较次数和移动次数来反应；另一个是执行算法所需要的附加存储单元的的多少。
插入排序：有一个已经有序的数据序列，要求在这个已经排好的数据序列中插入一个数，但要求插入后此数据序列仍然有序，这个时候就要用到一种新的排序方法——插入排序法,插入排序的基本操作就是将一个数据插入到已经排好序的有序数据中，从而得到一个新的、个数加一的有序数据，算法适用于少量数据的排序，时间复杂度为O(n^2)。是稳定的排序方法。插入算法把要排序的数组分成两部分：第一部分包含了这个数组的所有元素，但将最后一个元素除外（让数组多一个空间才有插入的位置），而第二部分就只包含这一个元素（即待插入元素）。在第一部分排序完成后，再将这个最后元素插入到已排好序的第一部分中。
插入排序的基本思想是：每步将一个待排序的纪录，按其关键码值的大小插入前面已经排序的文件中适当位置上，直到全部插入完为止。
void InsertSort(int *arr, size_t size)
{
    assert(arr);
    for (int i = 0; i < size - 1; ++i)
    {
        int tmp = arr[i+1];
        int end = i;
        while (end >= 0&&arr[end]>tmp)
        {
            arr[end + 1] = arr[end];
            --end;
        }
        arr[end + 1] = tmp;//即使都大于tmp,将tmp放置arr[0]处
    }
}

希尔排序：希尔排序(Shell Sort)是插入排序的一种。也称缩小增量排序，是直接插入排序算法的一种更高效的改进版本。希尔排序是非稳定排序算法。
希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止。
希尔排序是基于插入排序的以下两点性质而提出改进方法的：
插入排序在对几乎已经排好序的数据操作时，效率高，即可以达到线性排序的效率。

但插入排序一般来说是低效的，因为插入排序每次只能将数据移动一位。

先取一个小于n的整数d1作为第一个增量，把文件的全部记录分组。所有距离为d1的倍数的记录放在同一个组中。先在各组内进行直接插入排序；然后，取第二个增量d2<d1重复上述的分组和排序，直至所取的增量  =1(  <  …<d2<d1)，即所有记录放在同一组中进行直接插入排序为止。该方法实质上是一种分组插入方法。

void  ShellSort(int *arr, size_t size)
{
    assert(arr);
    int gap = size;
    while (gap>1)//注意跳出条件
    {
        gap = gap / 3 + 1;
        for (int i = 0; i < size - gap; ++i)//i可取到size-1-gap
        {
            int tmp = arr[i + gap];
            int end = i;
            while (end >= 0 && arr[end]>tmp)
            {
                arr[end + gap] = arr[end];
                end-=gap;
            }
            arr[end + gap] = tmp;//即使都大于tmp,将tmp放置arr[0]处
        }
    }
}

选择排序：选择排序（Selection sort）是一种简单直观的排序算法。它的工作原理是每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完。

n个记录的文件的直接选择排序可经过n-1趟直接选择排序得到有序结果：
①初始状态：无序区为R[1..n]，有序区为空。
②第1趟排序
在无序区R[1..n]中选出关键字最小的记录R[k]，将它与无序区的第1个记录R[1]交换，使R[1..1]和R[2..n]分别变为记录个数增加1个的新有序区和记录个数减少1个的新无序区。
……
③第i趟排序
第i趟排序开始时，当前有序区和无序区分别为R[1..i-1]和R(i..n）。该趟排序从当前无序区中选出关键字最小的记录 R[k]，将它与无序区的第1个记录R交换，使R[1..i]和R分别变为记录个数增加1个的新有序区和记录个数减少1个的新无序区。

思路：对比数组中前一个元素跟后一个元素的大小，如果后面的元素比前面的元素小则用一个变量k来记住他的位置，接着第二次比较，前面“后一个元素”现变成了“前一个元素”，继续跟他的“后一个元素”进行比较如果后面的元素比他要小则用变量k记住它在数组中的位置(下标)，等到循环结束的时候，我们应该找到了最小的那个数的下标了，然后进行判断，如果这个元素的下标不是第一个元素的下标，就让第一个元素跟他交换一下值，这样就找到整个数组中最小的数了。然后找到数组中第二小的数，让他跟数组中第二个元素交换一下值，以此类推。
void  SearchSort(int *arr, size_t size)
{
    assert(arr);
    for (int i = 0,j=size-1; i < j; ++i,-j)
    {
        int min = i;
        int max = j;
        for (int k = i; k<=j;++k)
        {
            if (arr[min]>arr[k])
                min = k;
            if (arr[max] < arr[k])
                max = k;
        }
        if (min != i)
        {
            int temp = arr[i];
            arr[i] = arr[min];
            arr[min] = temp;
 
            if (max == i) //如果最大值在最左边，肯定要被移走，此时要转移到相应的新位置 
            {
                max = min;
            }
        }
 
        if (max != j)
        {
            int tmp = arr[j];
            arr[j] = arr[max];
            arr[max] = tmp;
        }
    }
}

快速排序：快速排序（Quicksort）是对冒泡排序的一种改进。
快速排序由C. A. R. Hoare在1962年提出。它的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

在c++中可以用函数qsort（）可以直接为数组进行排序。
用 法:
void qsort(void *base, int nelem, int width, int (*fcmp)(const void *,const void *));
参数：
　　1 待排序数组首地址
　　2 数组中待排序元素数量
　　3 各元素的占用空间大小
　　4 指向函数的指针，用于确定排序的顺序。
int Quick_Sort(int *arr, int left, int right)
{
    assert(arr);
    if (left >= right)
        return right;
    int tmp = arr[right];
    int index = right;
    --right;
    while (left < right)
    {
        while (left < right&&arr[left] <= tmp)
            left++;
        while (left < right&&arr[right] >=tmp)
            right--;
        if (left < right)
            swap(arr[left], arr[right]);
    }
    if (arr[right] >= tmp)
        swap(arr[right], arr[index]);//重点
    return right;
}
void QuickSort(int* arr,int left,int right)
{
    assert(arr);
    if (left < right)
    {
        int mid = Quick_Sort(arr, left, right);
        QuickSort(arr, left, mid-1);
        QuickSort(arr, mid+1, right);
    }
     
}

冒泡排序：它重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。
这个算法的名字由来是因为越大的元素会经由交换慢慢“浮”到数列的顶端。
冒泡排序算法的运作如下：（从后往前）
比较相邻的元素。如果第一个比第二个大，就交换他们两个。

对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。

针对所有的元素重复���上的步骤，除了最后一个。

持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较

void BubbleSort(int* arr, size_t size)
{
    assert(arr);
    int flag = 0;
    for (int i = 0; i < size - 1; ++i)
    {
        flag = 0;
        for (int j = 0; j < size - i - 1;++j)
        {
            if (arr[j]>arr[j + 1])
            {
                swap(arr[j], arr[j + 1]);
            }
            flag = 1;
        }
        if (flag == 0)
            break;
    }
}

归并排序：归并排序（MERGE-SORT）是建立在归并操作上的一种有效的排序算法,该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。
归并过程为：比较a[i]和a[j]的大小，若a[i]≤a[j]，则将第一个有序表中的元素a[i]复制到r[k]中，并令i和k分别加上1；否则将第二个有序表中的元素a[j]复制到r[k]中，并令j和k分别加上1，如此循环下去，直到其中一个有序表取完，然后再将另一个有序表中剩余的元素复制到r中从下标k到下标t的单元。归并排序的算法我们通常用递归实现，先把待排序区间[s,t]以中点二分，接着把左边子区间排序，再把右边子区间排序，最后把左区间和右区间用一次归并操作合并成有序的区间[s,t]

归并操作(merge)，也叫归并算法，指的是将两个顺序序列合并成一个顺序序列的方法。
如　设有数列{6，202，100，301，38，8，1}
初始状态：6,202,100,301,38,8，1
第一次归并后：{6,202},{100,301},{8,38},{1}，比较次数：3；
第二次归并后：{6,100,202,301}，{1,8,38}，比较次数：4；
第三次归并后：{1,6,8,38,100,202,301},比较次数：4；
总的比较次数为：3+4+4=11,；
逆序数为14；

归并操作的工作原理如下：
第一步：申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列
第二步：设定两个指针，最初位置分别为两个已经排序序列的起始位置
第三步：比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置
重复步骤3直到某一指针超出序列尾
将另一序列剩下的所有元素直接复制到合并序列尾

/归并[)升序
//使用链表合并思想
void Merge(int* src, int* dest, int begin1, int end1, int begin2, int end2)
{
    assert(src&&dest);
    int index = begin1;//两个区间挨着
    while (begin1 < end1&&begin2 < end2)
    {
        if (src[begin1] < src[begin2])
        {
            dest[index++] = src[begin1++];
        }
        else
        {
            dest[index++] = src[begin2++];
        }
    }
    if (begin1 < end1)
    {
        while (begin1 < end1)
            dest[index++] = src[begin1++];
    }
    else
    {
        while (begin2 < end2)
            dest[index++] = src[begin2++];
    }
}
void _MergeSort(int* src, int* dst, int left, int right)
{
    if (left < right - 1)//[)
    {
        int mid = left + ((right - left) >> 1);
        _MergeSort(src, dst, left, mid);
        _MergeSort(src, dst, mid, right);
 
        Merge(src, dst, left, mid, mid, right);
        memcpy(src + left, dst + left, sizeof(int)*(right - left));
    }
}
void MergeSort(int *a, size_t size)
{
    int *dest = new int[size];
    _MergeSort(a, dest, 0, 10);
    delete[] dest;
}

基数排序：基数排序（radix sort）属于“分配式排序”（distribution sort），又称“桶子法”（bucket sort）或bin sort，顾名思义，它是透过键值的部份资讯，将要排序的元素分配至某些“桶”中，藉以达到排序的作用，基数排序法是属于稳定性的排序，其时间复杂度为O (nlog(r)m)，其中r为所采取的基数，而m为堆数，在某些时候，基数排序法的效率高于其它的稳定性排序法。

第一步
以LSD为例，假设原来有一串数值如下所示：
73, 22, 93, 43, 55, 14, 28, 65, 39, 81
首先根据个位数的数值，在走访数值时将它们分配至编号0到9的桶子中：
0
1 81
2 22
3 73 93 43
4 14
5 55 65
6
7
8 28
9 39

第二步
接下来将这些桶子中的数值重新串接起来，成为以下的数列：
81, 22, 73, 93, 43, 14, 55, 65, 28, 39
接着再进行一次分配，这次是根据十位数来分配：
0
1 14
2 22 28
3 39
4 43
5 55
6 65
7 73
8 81
9 93

第三步
接下来将这些桶子中的数值重新串接起来，成为以下的数列：
14, 22, 28, 39, 43, 55, 65, 73, 81, 93
这时候整个数列已经排序完毕；如果排序的对象有三位数以上，则持续进行以上的动作直至最高位数为
止。

//基数排序：利用哈希桶原理把数据排序，可选择从低位到高位或从高位到低位
//利用稀疏矩阵压缩存储进行数据定位
int  GetDigit(int* arr, size_t size)
{
    int maxDigit = 1;
    int maxNum = 10;
    for (int i = 0; i < size; ++i)
    {
        if (arr[i] >= maxNum)
        {
            int count = maxDigit;
            while (maxNum <= arr[i])
            {
                maxNum *= 10;
                ++count;
            }
            maxDigit = count;
        }
    }
    return maxDigit;
}
void LSDSort(int* arr, size_t size)//从低位开始排  MSD从高位开始排
{
    int counts[10] = { 0 };//存位数对应数据个数
    int startCounts[10] = { 0 };
    int *bucket = new int[size];
    int digit = 1;//表示先取各位
    int maxDigit = GetDigit(arr, size);
    int divider = 1;//除数
    while (digit++ <= maxDigit)
    {
        memset(counts, 0, sizeof(int) * 10);
        memset(startCounts, 0, sizeof(int) * 10);
        for (int i = 0; i < size; ++i)
            counts[(arr[i]/divider)% 10]++;
        for (int i = 1; i < 10; ++i)
            startCounts[i] = startCounts[i - 1] + counts[i - 1];
        for (int i = 0; i < size; ++i)
        {
            bucket[startCounts[(arr[i] / divider) % 10]++] = arr[i];
        }
        divider *= 10;
        memcpy(arr, bucket, sizeof(int)*size);
    }
    memcpy(arr, bucket, sizeof(int)*size);
    delete[] bucket;
}

计数排序：计数排序是一个非基于比较的排序算法，该算法于1954年由 Harold H. Seward 提出。它的优势在于在对一定范围内的整数排序时，它的复杂度为Ο(n+k)（其中k是整数的范围），快于任何比较排序算法。

计数排序对输入的数据有附加的限制条件：
1、输入的线性表的元素属于有限偏序集S；
2、设输入的线性表的长度为n，|S|=k（表示集合S中元素的总数目为k），则k=O(n)。
在这两个条件下，计数排序的复杂性为O(n)。
计数排序的基本思想是对于给定的输入序列中的每一个元素x，确定该序列中值小于x的元素的个数（此处并非比较各元素的大小，而是通过对元素值的计数和计数值的累加来确定）。
void CountSort(int *arr, size_t size,int len)
{
    int* bitMap = new int[len];
    memset(bitMap, 0, sizeof(int)*len);
    for (int i = 0; i < size; ++i)
    {
        int index = arr[i] >>5;//除以32
        int count = arr[i] % 32;
        bitMap[index] |= (1 << count);
         
    }
    int index = 0;
     
    for (int i = 0; i < len; ++i)
    {
        int count = 0;
        while (count <32&&index<size )
 
        {
            if (bitMap[i] & (1 << count))
                arr[index++] = i * 32 + count;
            ++count;
        }
    }
    delete[] bitMap;
}