八大常用排序

前言

一、插入排序

二、希尔排序

三、选择排序

四、堆排序

五、冒泡排序

六、快速排序

七、归并排序

八、计数排序

九、稳定性

前言

此篇博客都是以升序为例，降序只需更改部分地方即可，所以只排一个

一、插入排序

单趟排序

**如上图，在一个有序数组中插入一个6，只要找到比6小的数，此数后面的数往后挪动，然后在其后插入6即可 **

整个插入排序

外面只需套一层循环即可，为了保证不越界，所以i最多只能是倒数第二个元素的下标

如上图，起初可将第一个数看成是有序的，第二个数就是待插入的数，比它小就往前放，比它大就跳出循环，然后就是前2个数有序、前三个数有序……前n-1个数有序等等

二、希尔排序

希尔排序是在插入排序的基础上加强的

核心思路就是先分组，然后让每一组的数据都有序，最后再插入排序即可

设gap=3，即分3组

单趟排序与插入排序类似，只是把+1/-1改为了+gap/-gap，下图是第一组的排序

如下图，外面套一层for循环，就能把其它组进行排序了，循环判断条件n-gap,保证还留一组在外，i取不到，是为了保证不会越界，while循环是为了进行多次预排，gap=1时，就是插入排序

(也能不要while循环，直接将gap赋初值为3或其它数)

三、选择排序

如上图，采用的是头尾双指针，头指针找小，尾指针找到，然后两者交换即可

**如上图，最后面加一个if语句是为了防止第一个数就是最大数，会被换走 **

四、堆排序

首先得写一个向下调整的函数(向上调整也行)

因为是排升序，所以建大堆比较好

因为大堆根节点是最大的数，所以将其与最后一个数交换，然后将n-1个数向下调整又成为一个新的大堆，多次如此即排序完成，当只有一个数时，就不需要排了，因为它是第一个数，也是最小的数，后面的数都是有序数组了

五、冒泡排序

单趟排序

两个数比较大小，小的就放前面，大的放后面，往后如此，最大的数就放在最后了

整个排序

再往外套一个循环，有n个数，就得走n-1趟，而每一趟比较的次数也是逐渐-1

定义一个变量flag，赋初值为1,表示假设它有序，当有比较交换时就赋值为0，表示无序，当走完一趟，flag还是1，就表示有序了，直接break跳出循环，结束排序即可，所以flag能提高效率

六、快速排序

hoare版本

首先创建左右两个指针，选左边作key，右边先走，右指针找小于指向key的值，左指针找大于指向key的值，当两个指针相遇时结束，然后将指向key的值与相遇指向的哪个值交换，这样key指向的值，左边都小于它，右边都大于它，最后返回相遇的下标(右边作key，左边先走)

有=是因为当数组的数据全是同一个数时会死循环

要加left<right是防止越界，如5 4 3 2 1时，left就会一直+，从而越界

如果左边作key，左边先走，就会出问题，如下图

挖坑法

左边选key，还是右边先走，这次key是左边的第一个元素而不是下标，而坑位则是下标，起初是第一个元素的下标，当right遇到小时，就把该坐标的值赋值给坑位所在的数组成员，而该坐标则是新的坑位，同理，left也一样，left与right相遇结束，然后把key赋值给坑位所在的数组成员即可

前后指针法

选左做key，定义两个指针cur和prev，cur在前，prev在后，cur找小于key指向的数据，当cur指向的数值一直为小时，prev就一直紧跟着，二者不发生交换，当二者经过了有比key指向的数据大时，再遇到小于key指向的数据时，才发生交换，当cur指向的数据不再是数组中的数据时结束，最后将prev指向的数据与key指向的数据交换

整个排序(递归)

把一大区间的排序分成多个左右小区间来排序，当只有left>=right时就结束

整个排序(非递归)

得借助栈来保存区间的两个端点

首先先存储开始大区间的两个端点

因为栈是后进先出，所以先用begin存储先出来的数据，用end存储后出来的数据

然后就可以调用函数找keyi了

此时就能分成两个区间，一个是[begin,keyi-1],另一个是[keyi+1,end],然后再把这两个区间的端点都放到栈中去，再取出即可

循环判断条件是栈中是否还有数据，即栈是否为空，最后销毁栈即可

快速排序优化

可以从左中右三个位置取出中间大小的数，然后与左边的数交换，再选左做key，能使其分为相对均衡的两个小区间，提高效率，比如数组是1 4 7 3 5 2 8 6 9，排升序

七、归并排序

借助一个临时数组，将原数组分为2个区间，看成两个有序数组，再将其按照从小到大的顺序拷贝到临时数组中，而想要是有序数组，需要不断缩小区间，直到2个区间都各只有一个数时，就拷贝到临时数组中去，如下图

取中间坐标，将其化为小区间，再分别递归

两个区间从起始端点开始，逐渐比较大小，当有一个区间被拷贝完就结束循环

还有一个区间没拷贝完，所以仍需接着拷贝

拷贝完后，还需拷贝回原数组，因为需要从原数组中拿数据

如上图，一一归并后临时数组是2 4 3 7 1 6 9 11，原数组是4 2 3 7 6 1 9 11

两两归并时，两个区间都不是有序数组，就达不到目的，所以需拷贝回原数组

非递归

同样需借助临时数组

gap是分组，开始是分成n组，然后是n/2组等等，gap每次归完后是2，如一一归完后gap就2

一一归完后，二二归等等，所以要借助for循环，每次归完从头开始

index是拷贝到临时数组时，临时数组的下标

这里可以先每次归完后再拷贝回原数组，与递归有所差异

** **

只有数组的数据个数和满二叉树的数据一样多时，才不会出现越界问题，所以需考虑越界

有三种越界，end1，begin2，end3越界

begin2越界时，只要使右区间不存在，就不会出现越界和后面循环重复拷贝的情形

八、计数排序

首先要从数组中找到它的最大值和最小值，从而用相对的方式来计数，不至于浪费空间，比如如果只找最大值，假如是900，最小值却是600，如果从0开始就得开辟901个数据的空间，而用下标为0存600，就只需要301个数据的空间，同时需借助临时数组，以及用memset将其全部置为0

然后计数，如600，下标为0的元素就表示600，有几个600该元素就+几，605，下标为5的元素就是605等等

从最小的数据开始取数据，有几个就取几个

九、稳定性

概念：同大小的数据在数组中的相对位置，如果发生变化就表示不稳定，没有发生变化就表示稳定

如下图，就表示不稳定

插入排序、冒泡排序、归并排序是稳定的，没有改变相对位置

而希尔排序不稳定，因为涉及分组，所以相对位置会发生变化

堆排序不稳定，如下图

选择排序也不稳定，如下图

快速排序也不稳定，如下图

计数排序不稳定

十、全部代码

void swap(int* px, int* py)
{
    int tmp = *px;
    *px = *py;
    *py = tmp;
}

void Print(int* str, int sz)
{
    assert(str);
    int i = 0;
    for (i = 0; i < sz; i++)
    {
        printf("%d ", str[i]);
    }
    printf("\n\n");
}

void AdjustDown(int* str, int sz, int parent)
{
    int child = parent * 2 + 1;
    while (child < sz)
    {
        if (child + 1 < sz && str[child + 1] > str[child])
        {
            child++;
        }
        if (str[child] > str[parent])
        {
            swap(&str[child], &str[parent]);
            parent = child;
            child = parent * 2 + 1;
        }
        else
        {
            break;
        }
    }
}

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

void ShellSort(int* str, int sz)
{
    int i = 0;
    int gap = sz;
    while (gap > 1)
    {
        gap = gap / 2;
        for (i = 0; i < sz - gap; i++)
        {
            int end = i;
            int x = str[end + gap];
            while (end >= 0)
            {
                if (str[end] > x)
                {
                    str[end + gap] = str[end];
                    end -= gap;
                }
                else
                {
                    break;
                }
            }
            str[end + gap] = x;
        }
    }
}

void SelectSort(int* str, int sz)
{
    int left = 0;
    int right = sz - 1;
    int maxi = 0;
    int mini = 0;
    int i = 0;
    while (left < right)
    {
        maxi = left;
        mini = left;
        for (i = left; i <= right; i++)
        {
            if (str[i] > str[maxi])
            {
                maxi = i;
            }
            if (str[i] < str[mini])
            {
                mini = i;
            }
        }
        swap(&str[left], &str[mini]);
        if (left == maxi)
            maxi = mini;
        swap(&str[right], &str[maxi]);
        left++;
        right--;
    }
}

void HeapSort(int* str, int sz)
{
    int i = 0;
    for (i = (sz - 1 - 1) / 2; i >= 0; i--)
    {
        AdjustDown(str, sz, i);
    }
    int end = sz;
    while (end > 1)
    {
        swap(&str[0], &str[end - 1]);
        end--;
        AdjustDown(str, end, 0);
    }
}

void BubbleSort(int* str, int sz)
{
    int i = 0;
    for (i = 0; i < sz - 1; i++)
    {
        int j = 0;
        int flag = 1;
        for (j = 0; j < sz - 1; j++)
        {
            if (str[j] > str[j + 1])
            {
                swap(&str[j], &str[j + 1]);
                flag = 0;
            }
        }
        if (flag == 1)
        {
            break;
        }
    }
}

int GetMid(int* str, int left, int right)
{
    int mid = (left + right) / 2;
    if (str[left] < str[right])
    {
        if (str[left] < str[mid])
            return mid;
        else if (str[left] > str[mid])
            return left;
        else
            return right;
    }
    else
    {
        if (str[left] < str[mid])
            return left;
        else if (str[right] > mid)
            return right;
        else
            return mid;
    }
}

int Partion1(int* str,int left,int right)
{
    int mid = GetMid(str, left, right);
    swap(&str[mid], &str[left]);
    int keyi = left;
    while (left < right)
    {
        while (left < right && str[right] >= str[keyi])
        {
            right--;
        }
        while (left < right && str[left] <= str[keyi])
        {
            left++;
        }
        swap(&str[left], &str[right]);
    }
    swap(&str[left], &str[keyi]);
    return left;
}

int Partion2(int* str, int left, int right)
{
    int mid = GetMid(str, left, right);
    swap(&str[mid], &str[left]);
    int key = str[left];
    int hole = left;
    while (left < right)
    {
        while (left < right && str[right] >= key)
        {
            right--;
        }
        str[hole] = str[right];
        hole = right;
        while (left < right && str[left] <= key)
        {
            left++;
        }
        str[hole] = str[left];
        hole = left;
    }
    str[hole] = key;
    return hole;
}

int Partion3(int* str, int left, int right)
{
    int mid = GetMid(str, left, right);
    swap(&str[mid], &str[left]);
    int keyi = left;
    int prev = left;
    int cur = prev + 1;
    while (cur <= right)
    {
        if (str[cur] < str[keyi] && cur != ++prev)
        {
            swap(&str[cur], &str[prev]);
        }
        cur++;
    }
    swap(&str[prev], &str[keyi]);
    return prev;
}

void QuickSort(int* str,int left,int right)
{
    if (left >= right)
        return;
    int keyi = Partion3(str, left, right);
    QuickSort(str, left, keyi - 1);
    QuickSort(str, keyi + 1, right);
}

void QuickSortNonR(int* str,int left,int right)
{
    ST st;
    STInit(&st);
    STPushTop(&st, right);
    STPushTop(&st, left);
    while (!STEmpty(&st))
    {
        int begin = STTop(&st);
        STPopTop(&st);
        int end = STTop(&st);
        STPopTop(&st);
        int keyi = Partion3(str, begin, end);

        if (end > keyi + 1)
        {
            STPushTop(&st, end);
            STPushTop(&st, keyi + 1);
        }
        if (begin < keyi - 1)
        {
            STPushTop(&st, keyi - 1);
            STPushTop(&st, begin);
        }
    }
    STDestroy(&st);
}

void _MergeSort(int* str, int left, int right, int* tmp)
{
    if (left >= right)
        return;
    int mid = (left + right) / 2;
    _MergeSort(str,left, mid, tmp);
    _MergeSort(str, mid + 1, right, tmp);
    int begin1 = left;
    int begin2 = mid + 1;
    int end1 = mid;
    int end2 = right;
    int i = left;
    while (begin1 <= end1 && begin2 <= end2)
    {
        if (str[begin1] < str[begin2])
        {
            tmp[i++] = str[begin1++];
        }
        else
        {
            tmp[i++] = str[begin2++];
        }
    }
    while (begin1 <= end1)
    {
        tmp[i++] = str[begin1++];
    }
    while (begin2 <= end2)
    {
        tmp[i++] = str[begin2++];
    }
    int j = left;
    for (j = left; j < i; j++)
    {
        str[j] = tmp[j];
    }
}

void MergerSort(int* str, int left, int right)
{
    int* tmp = (int*)malloc(sizeof(int) * (right + 1));
    if (tmp == NULL)
    {
        printf("malloc fail\n");
        exit(-1);
    }
    _MergeSort(str, left, right,tmp);
    free(tmp);
    tmp = NULL;
}

void MergerSortNonR(int* str, int left, int right)
{
    int* tmp = (int*)malloc(sizeof(int) * (right + 1));
    if (tmp == NULL)
    {
        printf("malloc fail\n");
        exit(-1);
    }
    int i = 0;
    int gap = 1;
    while (gap <= right)
    {
        for (i = 0; i < right; i += 2 * gap)
        {
            int begin1 = i;
            int end1 = i + gap - 1;
            int begin2 = i + gap;
            int end2 = i + 2 * gap - 1;
            int index = i;
            //end1越界
            if (end1 > right)
            {
                end1 = right;
            }
            //begin2越界
            if (begin2 > right)
            {
                begin2 = end2 + 1;
            }
            //end2越界
            if (end2 > right)
            {
                end2 = right;
            }
            while (begin1 <= end1 && begin2 <= end2)
            {
                if (str[begin1] < str[begin2])
                {
                    tmp[index++] = str[begin1++];
                }
                else
                {
                    tmp[index++] = str[begin2++];
                }
            }
            while (begin1 <= end1)
            {
                tmp[index++] = str[begin1++];
            }
            while (begin2 <= end2)
            {
                tmp[index++] = str[begin2++];
            }
        }
        int j = 0;
        for (j = 0; j <= right; j++)
        {
            str[j] = tmp[j];
        }
        gap *= 2;
    }    
    free(tmp);
    tmp = NULL;
}

void CountSort(int* str, int sz)
{
    int max = str[0];
    int min = str[0];
    int i = 0;
    for (i = 1; i < sz; i++)
    {
        if (str[i] > max)
            max = str[i];
        if (str[i] < min)
            min = str[i];
    }
    int* count = (int*)malloc(sizeof(int) * (max - min + 1));
    if (count == NULL)
    {
        printf("malloc fail\n");
        exit(-1);
    }
    memset(count, 0, sizeof(int) * (max - min + 1));
    for (i = 0;i < sz;i++)
    {
        count[str[i] - min]++;
    }
    i = 0;
    int j = 0;
    while(i < sz)
    {
        while (count[j]-- && j <= max - min)
        {
            str[i++] = min + j;
        }
        j++;
    }
}