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

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

稳定性 ：假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中，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++;
}