排序：插入、选择、交换、归并排序

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

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

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

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

#pragma once
#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
#include <time.h>
#include <string.h>
#include <memory.h>

//打印
void PrintArray(int* a, int n);

// 排序实现的接口
// 插入排序
void InsertSort(int* a, int n);

// 希尔排序
void ShellSort(int* a, int n);

// 选择排序
void SelectSort(int* a, int n);

// 堆排序
void AdjustDwon(int* a, int n, int root);
void HeapSort(int* a, int n);

// 冒泡排序
void BubbleSort(int* a, int n);

// 快速排序递归实现
// 快速排序hoare版本
int PartSort1(int* a, int begin, int end);

//三数取中
int GetMidindex(int* a, int begin, int end);

// 快速排序挖坑法
int PartSort2(int* a, int begin, int end);

// 快速排序前后指针法
int PartSort3(int* a, int begin, int end);
void QuickSort(int* a, int left, int right);

// 快速排序 非递归实现
void QuickSortNonR(int* a, int left, int right);

// 归并排序递归实现
void MergeSort(int* a, int n);

// 归并排序非递归实现
void MergeSortNonR(int* a, int n);

// 计数排序
void CountSort(int* a, int n);

#define _CRT_SECURE_NO_WARNINGS 1
#include "Sort.h"
#include "Stack.h"
//打印
void PrintArray(int* a, int n)
{
    int i = 0;
    for (i = 0; i < n; i++)
    {
        printf("%d ", a[i]);
    }
    printf("\n");
}

//插入排序  O(N^2)
void InsertSort(int* a, int n)
{
    assert(a);
    int i = 0;
    for (i = 0; i < n - 1; i++)
    {
        int end = i;
        int tmp = a[end + 1];
        //将end+1的数据插入到[0,end]有序数组中
        while (end >= 0)
        {
            if (tmp < a[end])
            {
                a[end + 1] = a[end];
                end--;
            }
            else
            {
                break;
            }
        }
        a[end + 1] = tmp;
    }
}

// 希尔排序  O(N^1.3  N^2)
void ShellSort(int* a, int n)
{
    assert(a);
    //1. gap > 1 相当于预排序，让数组接近有序
    //2. gap==1就相当于直接插入排序，保证有序
    int gap = n;
    while (gap > 1)
    {
        gap = gap / 3 + 1;//+1是保证最后一次排序gap等于1
        //gap==1，最后一次就相当于直接插入排序
        int i = 0;
        for (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 = end - gap;
                }
                else
                {
                    break;
                }
            }
            a[end + gap] = tmp;
        }
        //PrintArray(a, n);
    }
}

void Swap(int* p1, int* p2)
{
    int tmp = *p1;
    *p1 = *p2;
    *p2 = tmp;
}

// 选择排序
// O(N^2)
void SelectSort(int* a, int n)
{
    assert(a);
    int begin = 0;
    int end = n - 1;
    while (begin < end)
    {
        int maxi = begin;
        int mini = begin;
        int i = 0;
        for (i = begin + 1; i <= end; i++)
        {
            if (a[i] > a[maxi])
            {
                maxi = i;
            }

            if (a[i] < a[mini])
            {
                mini = i;
            }
        }
        Swap(&a[mini], &a[begin]);
        //maxi和begin的位置重叠,maxi的位置需要修正
        if (maxi == begin)//max被换走了
        {
            maxi = mini;//找到max
        }
        Swap(&a[maxi], &a[end]);
        begin++;
        end--;
    }
}

// 堆排序
void AdjustDwon(int* a, int n, int root)
{
    int parent = root;
    int child = parent * 2 + 1;
    while (child < n)
    {
        //选出较大的孩子
        if (a[child + 1] > a[child] && child + 1 < n)
        {
            child++;
        }
        if (a[child] > a[parent])
        {
            Swap(&a[parent], &a[child]);
            parent = child;
            child = parent * 2 + 1;
        }
        else
        {
            break;
        }
    }
}

void HeapSort(int* a, int n)
{
    //排升序，建大堆还是小堆？
    int i = 0;
    for (i = (n - 1 - 1) / 2; i >= 0 ; i--)
    {
        AdjustDwon(a, n, i);
    }
    int end = n - 1;
    while (end > 0)
    {
        Swap(&a[0], &a[end]);
        AdjustDwon(a, end, 0);
        --end;
    }
}

// 冒泡排序 O(N^2)
void BubbleSort(int* a, int n)
{
    int flag = 1;
    int i = 0;
    for (i = 0; i < n; i++)
    {
        int j = 0;
        for (j = 0; j < n - 1 - i; j++)
        {
            if (a[j] > a[j + 1])
            {
                Swap(&a[j], &a[j + 1]);
                flag = 0;
            }
        }
        //如果一趟冒泡排序过程中没有发生交换，则已经有序，不需要再进行冒泡排序
        if (flag == 1)
        {
            break;
        }
    }
}

//三数取中
int GetMidindex(int* a, int begin, int end)
{
    int mid = (begin + end) / 2 ;
    if (a[begin] < a[mid])
    {
        if (a[mid] < a[end])
        {
            return mid;
        }
        else if (a[begin] > a[end])
        {
            return begin;
        }
        else
        {
            return end;
        }
    }
    else//a[begin] > a[mid]
    {
        if (a[mid] > a[end])
        {
            return mid;
        }
        else if (a[begin] < a[end])
        {
            return begin;
        }
        else
        {
            return end;
        }
    }
}

//左右指针法
int PartSort1(int* a, int begin, int end)
{
    int mid = GetMidindex(a, begin, end);
    Swap(&a[mid], &a[end]);
    int keyindex = end;//右边做key
    while (begin < end)
    {
        //左边先走,//left < right防止在++的时候超出，而错过相遇
        while (begin < end && a[begin] <= a[keyindex])//左边找比key大,
        {
            begin++;
        }

        //右边找比key小
        while (begin < end && a[end] >= a[keyindex])
        {
            end--;
        }

        //交换left和right位置的值
        Swap(&a[begin], &a[end]);
    }
    //交换key和相遇位置的值
    Swap(&a[begin], &a[keyindex]);
    return begin;
}

// 快速排序挖坑法
int PartSort2(int* a, int begin, int end)
{
    int mid = GetMidindex(a, begin, end);
    Swap(&a[mid], &a[end]);
    //坑
    int key = a[end];
    while (begin < end)
    {
        //左边找比key大的
        while (begin < end && a[begin] <= key)
        {
            begin++;
        }
        //将找到的数填在end位置，然后形成新的坑
        a[end] = a[begin];

        //右边找比key小的数
        while (begin < end && a[end] >= key)
        {
            end--;
        }
        //将找到的数填在begin的位置，然后形成新的坑
        a[begin] = a[end];
    }
    //begin和end相遇，循环结束，将key的值填入begin的位置
    a[begin] = key;
    return begin;
}

// 快速排序前后指针法
int PartSort3(int* a, int begin, int end)
{
    int mid = GetMidindex(a, begin, end);
    Swap(&a[mid], &a[end]);
    int key = a[end];
    int keyindex = end;
    int cur = begin;
    int prev = begin - 1;;
    while (cur < end)
    {
        while (a[cur] <= a[keyindex] && ++prev != cur)
        {
            Swap(&a[cur], &a[prev]);
        }

         ++cur;
    }
    
    Swap(&a[++prev], &a[keyindex]);

    return prev;
}

//时间复杂度O(N*log N)
//空间复杂度 O(log N)
void QuickSort(int* a, int left, int right)
{
    assert(a);
    //[left,div-1] , [div+1,right]
    if (left >= right)
        return;

    if ((right - left + 1) > 10)
    {
        //int div = PartSort1(a, left, right);
        //int div = PartSort2(a, left, right);
        int div = PartSort3(a, left, right);

        //PrintArray(a+left, right-left+1);
        //printf("[%d %d] %d [%d %d]", left, div - 1, div, div + 1, right);
        //printf("\n");

        QuickSort(a, left, div - 1);
        QuickSort(a, div + 1, right);
    }

    else
    {
        //小于等于10个数，直接选插入排序,不在递归排序
        InsertSort(a + left, right - left + 1);
    }

}

// 快速排序 非递归实现
//递归改非递归  
//-->1.改循环（斐波拉契数列求解），一些简单递归才能改循环
//-->2.栈模拟存储数据非递归
//非递归：1.提高效率（递归建立栈还是有消耗的，但是对于现代的计算机，这个优化微乎其微，可以忽略不计）
//       2.递归的最大缺陷是，如果栈的深度太深，可能会导致栈溢出，因为系统栈空间一般不大，在M级别
//       数据结构模拟非递归，数据是存储在堆上的，堆是G级别的空间

void QuickSortNonR(int* a, int left, int right)
{
    assert(a);
    //栈来实现快速排序
    Stack st;//定义栈
    StackInit(&st);

    //先入右边，在入左边
    StackPush(&st, right);
    StackPush(&st, left);

    while (!StackEmpty(&st))
    {
        int begin = StackTop(&st);//左边
        StackPop(&st);//先出一个

        int end = StackTop(&st);
        StackPop(&st);

        int div = PartSort1(a, begin, end);

        //先处理左边
        if (begin < div - 1)//左边至少有两个数据
        {
            StackPush(&st, div - 1);
            StackPush(&st, begin);
        }

        //处理右边
        if (end > div + 1)//至少有两个数据
        {
            StackPush(&st, end);
            StackPush(&st, div + 1);
        }
    }
    //销毁栈，防止内存泄漏
    StackDestory(&st);
}

void _MergeArray(int* a, int begin1, int end1, int begin2, int end2, int* tmp)
{
    //递归完了得到两个有序数组
    //归并
    int left = begin1;
    int right=end2;
    int index = begin1;
    while (begin1 <= end1 && begin2 <= end2)
    {
        if (a[begin1] < a[begin2])
        {
            tmp[index] = a[begin1];
            index++;
            begin1++;
        }
        else
        {
            tmp[index] = a[begin2];
            index++;
            begin2++;
        }
    }
    //应该还有一个数组还有剩余元素
    while (begin1 <= end1)
    {
        tmp[index++] = a[begin1++];
    }

    while (begin2 <= end2)
    {
        tmp[index++] = a[begin2++];
    }

    //把归并好的在tmp数组的元素拷贝回原来数组a
    int i = 0;
    for (i = left; i <= right; i++)
    {
        a[i] = tmp[i];
    }
}

void _MergeSort(int* a, int left, int right, int* tmp)
{
    //递归截止条件
    if (left >= right)
    {
        return;
    }
        
    //先递归
    int mid = (left + right) / 2;
    //[left,mid],[mid+1,right]
    _MergeSort(a, left, mid, tmp);
    _MergeSort(a, mid + 1, right, tmp);
    _MergeArray(a, left, mid, mid + 1, right, tmp);
    
}

// 归并排序递归实现
//时间复杂度 O(N*logN)
//空间复杂度 O(N)
void MergeSort(int* a, int n)
{
    assert(a);
    int* tmp = (int*)malloc(sizeof(int) * n);
    if (tmp == NULL)
    {
        printf("申请内存失败\n");
        exit(-1);
    }
    _MergeSort(a, 0, n - 1, tmp);
    free(tmp);//释放内存，防止内存泄漏
}

// 归并排序非递归实现
void MergeSortNonR(int* a, int n)
{
    assert(a);
    int* tmp = (int*)malloc(sizeof(int) * n);
    int gap = 1;
    while (gap < n)
    {
        int i = 0;
        for (i = 0; i < n; i = i + 2 * gap)
        {
            //使用闭区间
            //[i,i+gap-1],[i+gap,i+2*gap-1]
            int begin1 = i;
            int end1 = i + gap - 1;
            int begin2 = i + gap;
            int end2 = i + 2 * gap - 1;
            //1、合并时只有第一组，第二组不需要合并
            if (begin2 >= n)
            {
                break;
            }
            //2、合并时第二组只有部分数据，需要修改边界值
            if (end2 >= n)
            {
                end2 = n - 1;
            }
            _MergeArray(a, begin1, end1, begin2, end2, tmp);
        }
        gap = gap * 2;
        PrintArray(a, n);
    }
}

//计数排序
//时间复杂度O(N+range)
//空间复杂度O(range)
//只适用于整型，浮点型和字符串还是需要使用比较排序
void CountSort(int* a, int n)
{
    assert(a);
    //找出最大值和最小值
    int min = a[0];
    int max = a[0];
    
    for (int i = 0; i < n; i++)
    {
        if (a[i] > max)
        {
            max = a[i];
        }

        if (a[i] < min)
        {
            min = a[i];
        }
    }

    int range = max - min + 1;
    //开辟一个数组
    int* countArray = (int*)malloc(sizeof(int) * range);

    //设置为0
    memset(countArray, 0, sizeof(int) * range);

    //统计次数
    for (int i = 0; i < n ; ++i)
    {
        countArray[a[i] - min]++;
    }

    //排序
    int index = 0;
    for (int j = 0; j < range; ++j)
    {
        while (countArray[j]--)
        {
            a[index++] = j + min;
        }
    }
    free(countArray);
}

#define _CRT_SECURE_NO_WARNINGS 1
#include "Sort.h"
#include "Stack.h"

void TestInsertSort()
{
    int a[] = { 2,1,4,3,9,6,4,0,5,8 };
    int sz = sizeof(a) / sizeof(a[0]);
    PrintArray(a, sz);
    InsertSort(a, sz);
    PrintArray(a, sz);
}

TestShellSort()
{
    int a[] = { 20,19,18,17,16,15,14,13,12,11,10,9,8,7,6,5,4,3,2,1,0 };
    int sz = sizeof(a) / sizeof(a[0]);
    PrintArray(a, sz);
    ShellSort(a, sz);
    PrintArray(a, sz);
}

void TestSelectSort()
{
    int a[] = { 20,19,18,17,16,15,14,13,12,11,10,9,8,7,6,5,4,3,2,1,0 };
    int sz = sizeof(a) / sizeof(a[0]);
    PrintArray(a, sz);
    SelectSort(a, sz);
    PrintArray(a, sz);
}

void TestHeapSort()
{
    int a[] = { 20,19,18,17,16,15,14,13,12,11,10,9,8,7,6,5,4,3,2,1,0 };
    int sz = sizeof(a) / sizeof(a[0]);
    PrintArray(a, sz);
    HeapSort(a, sz);
    PrintArray(a, sz);
}

void TestBubbleSort()
{
    int a[] = { 20,19,18,17,16,15,14,13,12,11,10,9,8,7,6,5,4,3,2,1,0 };
    int sz = sizeof(a) / sizeof(a[0]);
    PrintArray(a, sz);
    BubbleSort(a, sz);
    PrintArray(a, sz);
}

void TestQuickSort()
{
    //int a[] = { 20,19,18,17,16,15,14,13,12,11,10,9,8,7,6,5,4,3,2,1,0 };
    int a[] = { 2,1,4,3,9,6,4,0,5,8 };
    int sz = sizeof(a) / sizeof(a[0]);
    PrintArray(a, sz);
    QuickSort(a, 0,sz-1);
    PrintArray(a, sz);
}

void TestQuickSortNonR()
{
    //int a[] = { 20,19,18,17,16,15,14,13,12,11,10,9,8,7,6,5,4,3,2,1,0 };
    int a[] = { 2,1,4,3,9,6,4,0,5,8 };
    int sz = sizeof(a) / sizeof(a[0]);
    PrintArray(a, sz);
    QuickSortNonR(a, 0, sz - 1);
    PrintArray(a, sz);
}

void TestMergeSort()
{
    //int a[] = { 20,19,18,17,16,15,14,13,12,11,10,9,8,7,6,5,4,3,2,1,0 };
    int a[] = { 10,6,7,1,3,9,4,2 };
    int sz = sizeof(a) / sizeof(a[0]);
    PrintArray(a, sz);
    MergeSort(a, sz);//不是sz-1，如果是sz-1,会导致最后一个元素没有排到
    PrintArray(a, sz);
}

void TestMergeSortNonR()
{
    //int a[] = { 20,19,18,17,16,15,14,13,12,11,10,9,8,7,6,5,4,3,2,1,0 };
    int a[] = { 10,6,7,1,3,9,4 };
    int sz = sizeof(a) / sizeof(a[0]);
    //PrintArray(a, sz);
    MergeSortNonR(a, sz);//不是sz-1，如果是sz-1,会导致最后一个元素没有排到
    //PrintArray(a, sz);
}

void TestCountSort()
{
    //int a[] = { 20,19,18,17,16,15,14,13,12,11,10,9,8,7,6,5,4,3,2,1,0 };
    int a[] = { 10,6,7,1,3,9,4 };
    int sz = sizeof(a) / sizeof(a[0]);
    PrintArray(a, sz);
    CountSort(a, sz);//不是sz-1，如果是sz-1,会导致最后一个元素没有排到
    PrintArray(a, sz);
}

void TestOP()
{
    srand(time(0));
    const int N = 100000;

    int* a1 = (int*)malloc(sizeof(int) * N);
    int* a2 = (int*)malloc(sizeof(int) * N);
    int* a3 = (int*)malloc(sizeof(int) * N);
    int* a4 = (int*)malloc(sizeof(int) * N);
    int* a5 = (int*)malloc(sizeof(int) * N);
    int* a6 = (int*)malloc(sizeof(int) * N);
    for (int i = 0; i < N; ++i)
    {
        a1[i] = rand();
        a2[i] = a1[i];
        a3[i] = a1[i];
        a4[i] = a1[i];
        a5[i] = a1[i];
        a6[i] = a1[i];
    }

    int begin1 = clock();
    InsertSort(a1, N);
    int end1 = clock();

    int begin2 = clock();
    ShellSort(a2, N);
    int end2 = clock();

    int begin3 = clock();
    SelectSort(a3, N);
    int end3 = clock();

    int begin4 = clock();
    HeapSort(a4, N);
    int end4 = clock();

    int begin5 = clock();
    BubbleSort(a5, N);
    int end6 = clock();

    int begin7 = clock();
    QuickSort(a5, 0, N-1);
    int end8 = clock();

    int begin9 = clock();
    QuickSortNonR(a5, 0, N - 1);
    int end10 = clock();
    /*int begin5 = clock();
    QuickSort(a5, 0, N - 1);
    int end5 = clock();

    int begin6 = clock();
    MergeSort(a6, N);
    int end6 = clock();*/

    //printf("InsertSort:%d\n", end1 - begin1);
    printf("ShellSort:%d\n", end2 - begin2);
    printf("SelectSort:%d\n", end3 - begin3);
    printf("HeapSort:%d\n", end4 - begin4);
    //printf("BubbleSort:%d\n", end6 - begin5);
    printf("QuickSort:%d\n", end8 - begin7);
    printf("QuickSortNonR:%d\n", end10 - begin9);

    /*printf("QuickSort:%d\n", end5 - begin5);
    printf("MergeSort:%d\n", end6 - begin6);
    free(a1);
    free(a2);
    free(a3);
    free(a4);
    free(a5);
    free(a6);*/
}

int main()
{
    //TestInsertSort();
    //TestShellSort();
    //TestSelectSort();
    //TestHeapSort();

    //TestBubbleSort();
    //TestQuickSort();
    //TestQuickSortNonR();
    //TestMergeSort();
    
    //TestMergeSortNonR();
    //MergeSortFile("Sort.txt");
    TestCountSort();
    
    //TestOP();
    return 0;

}

#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
//用数组来实现

//静态的数组
//#define N 10
//struct Stack
//{
//    int _a[N];
//    int _top;
//};

//动态的数组
typedef int STDataType;
typedef struct Stack 
{
    STDataType* _a;
    int _top;//栈顶下标
    int _capacity;
}Stack;

//初始化
void StackInit(Stack* pst);

//销毁
void StackDestory(Stack* pst);

//入栈
void StackPush(Stack* pst, STDataType x);

//出栈
void StackPop(Stack* pst);

//获取数据个数
int StackSize(Stack* pst);

//返回1是空，返回0是非空
int StackEmpty(Stack* pst);

//获取栈顶的数据
STDataType StackTop(Stack* pst);

#define _CRT_SECURE_NO_WARNINGS 1
#include "Stack.h"
//初始化
void StackInit(Stack* pst)
{
    assert(pst);

    //pst->_a = NULL;
    //pst->_top = 0;
    //pst->_capacity = 0;
    pst->_a = (STDataType*)malloc(sizeof(STDataType) * 4);
    pst->_top = 0;
    pst->_capacity = 4;
}

//销毁
void StackDestory(Stack* pst)
{
    assert(pst);
    free(pst->_a);
    pst->_a = NULL;
    pst->_top = 0;
    pst->_capacity = 0;
}

//入栈
void StackPush(Stack* pst, STDataType x)
{
    assert(pst);
    if (pst->_top == pst->_capacity)//满了需要增容
    {
        pst->_capacity *= 2;
        STDataType* tmp = (STDataType*)realloc(pst->_a, pst->_capacity*sizeof(STDataType) );
        if (tmp == NULL)//增容失败
        {
            printf("增容失败\n");
            exit(-1);
        }
        else//将tmp给pst->_a,指向它
        {
            pst->_a = tmp;
        }
    }
    pst->_a[pst->_top] = x;
    pst->_top++;
}

//出栈
void StackPop(Stack* pst)
{
    assert(pst);
    assert(pst->_top > 0);
    --pst->_top;
}

//获取数据个数
int StackSize(Stack* pst)
{
    assert(pst);
    return pst->_top;
}

//返回1是空，返回0是非空
int StackEmpty(Stack* pst)
{
    assert(pst);
    return pst->_top == 0 ? 1 : 0;
}

//获取栈顶的数据
STDataType StackTop(Stack* pst)
{
    assert(pst);
    assert(pst->_top > 0);
    return pst->_a[pst->_top - 1];//pst->_top是元素的个数
}