排序(交换排序：快排)

快速排序：
写快排的注意事项
1.单趟排序hoare
2.不写优化只说优化就行
理想的情况下：每次排序都是二分，直到二分到最后，那就相当于递归高度次(logN)，每一层单趟排都是O(N)，时间复杂度O(NlogN) 空间复杂度就是递归的深度 O(logN)
最坏的情况：数组有序（或者接近有序）是最坏情况。假如数组是升序，key是left，要排升序，有N层，则每层都排(N,N-1,N-2…,3,2,1)，时间复杂度是O(NN)。因此，优化最差情况1.三数取中 2.小区间排序优化
在这里插入图片描述
相遇有两种情况：right找left或者left找right
如果是right先走，最坏在遇见left的时候停止，而这个位置是left的位置，值肯定是比key小的，但left先走的话，最坏情况遇见right，此时值是比key大的，交换会出问题。因此，left是key需要让right先走。

void QuickSort(int* a,int n)
{int left = 0, right = n-1;int keyi = left;while(left < right){// 找小// 如果没有left < right可能会导致right一直--,越界访问eg：[1,2,3,4,5]while(left < right && a[right] >= a[keyi]) --right;// 找大//如果没有a[left] <= a[keyi]的=符号时，可能会导致死循环eg:[5,1,2,5,6];while(left < right && a[left] <= a[keyi]) ++left;Swap(&a[left], &a[right]);}Swap(&a[keyi], &a[left]);
}

第二阶段：分治（递归），对每次的key的左右区间看成子问题，传入递归一直分治，最终完成。递归结束标志：当这个子区间不存在或者只有单个值时返回。
在这里插入图片描述

void QuickSort(int* a, int begin, int end)
{if(begin >= end) // 迭代的终点：左区间>=右区间时，迭代结束。return;int left = begin, right = end-1;int keyi = left;while(left < right){// 找小while(left < right && a[right] >= a[keyi])--right;// 找大while(left < right && a[left] <= a[keyi])++left;Swap(&a[left], &a[right]);}int meeti = left;Swap(&a[keyi], &a[meeti]);//左：[begin,meeti-1] meeti 右：[meeti+1,end]QuickSort(a, begin, meeti-1); // 传参就是[0, n-1]QuickSort(a, meeti+1, end);
}

挖坑法(代码在后面)：将key的位置看作是一个坑(hole)，然后利用part1的思路，找到大的将值放进坑中，然后此时right就是hole，再找小的值，将小的值放进hole中，此时left是坑…,直到相遇，把最早的key值放进相遇的坑中。
挖坑法的初次排序后的值可能和hoare的值不同。
在这里插入图片描述

前后指针法(代码在后面)：cur找比keyi位置小的值，找到后prev++，再交换prev和cur的值，直到cur走到数组尾，然后将keyi和prev的位置的值交换。
在这里插入图片描述

快排最差情况的优化1：（防止最坏的情况）
三数取中：对快排影响最大的是key，如果key取值越接近中位数则越接近二分，效率越高
三数取中是在最左边，左右边和最中间的值，选择他们三个不是最大也不是最小的数。
三数取中，将需要的那个中间的数换到最左边的位置，这样就不用操心key位置变换的问题了。

 // 快速排序的三数取中 优化快排的最差情况
int GetMidIndex(int* a, int left, int right)
{int mid = (left + right) >> 1; //就是(left + right)/2// left, mid, rightif(a[left] < a[mid]){if(a[mid] < a[right])return mid;else if(a[left] > a[right])return left;elsereturn right;}else // a[left] > a[mid]{if(a[mid] > a[right])return mid;else if(a[left] < a[right])return left;elsereturn right;}
}
// 快速排序hoare版本 -- 最原始的 左右指针法
int PartSort1(int* a, int left, int right)
{int midIndex = GetMidIndex(a, left, right); //找到中间数Swap(&a[left], &a[midIndex]); //再交换到left位置int keyi = left;while(left < right){// 找小while(left < right && a[right] >= a[keyi])--right;// 找大while(left < right && a[left] <= a[keyi])++left;Swap(&a[left], &a[right]);}Swap(&a[keyi], &a[left]);return left;
}
// 迭代过程
void QuickSort(int* a, int begin, int end)
{if(begin >= end) // 迭代的终点：左区间>=右区间时，迭代结束。return;int keyi = PartSort1(a, begin, end);//左：[begin,keyi -1] keyi 右：[keyi +1,end]QuickSort(a, begin, keyi -1); // 传参就是[0, n-1]QuickSort(a, keyi +1, end);
}

快排最差情况的优化2：（防止最后递归太多）
小区间优化：对于最后面几个数的排序不再进行递归，直接选择插入排序对最后几个数进行排序。（作用不大）

// 迭代过程
void QuickSort(int* a, int begin, int end)
{if(begin >= end) // 迭代的终点：左区间>=右区间时，迭代结束。return;// 如果子区间数据较多继续选key单趟，分割子区间分治递归if(end - begin > 20){int keyi = PartSort1(a, begin, end);//左：[begin,keyi -1] keyi 右：[keyi +1,end]QuickSort(a, begin, keyi -1); // 传参就是[0, n-1]QuickSort(a, keyi +1, end);}else //如果子区间数很少了还要进行递归就很不划算。{//数据少了直接使用插入排序算法。  插入排序传的是数组和元素个数。InsortSort(a+begin, end-begin+1); }
}

将快排中的单趟排序独立出来

// 快速排序hoare版本 -- 最原始的 左右指针法
int PartSort1(int* a, int left, int right)
{int keyi = left;while(left < right){// 找小while(left < right && a[right] >= a[keyi])--right;// 找大while(left < right && a[left] <= a[keyi])++left;Swap(&a[left], &a[right]);}Swap(&a[keyi], &a[left]);return left;
}
//挖坑法：
int PartSort2(int* a, int left, int right)
{int midIndex = GetMidIndex(a, left, right); //找到中间数Swap(&a[left], &a[midIndex]); //再交换到left位置int key = a[left];while(left < right){//找小while(left < right && a[right] >= key )right--;// 放到左边的坑位，右边就是新的坑a[left] = a[right];//找大while(left < right && a[left] <= key )left++;//放到右边的坑位，左边就是新的坑a[right] = a[left];}a[left] = key;return left;
}
// 快速排序前后指针法
int PartSort3(int* a, int left, int right)
{int midIndex = GetMidIndex(a, left, right); //找到中间数Swap(&a[left], &a[midIndex]); //再交换到left位置int keyi = left;int prev = left, cur = prev+1;while(cur <= right){if(a[cur] < a[key]){prev++;if(prev != cur){Swap(&a[cur], &a[prev]);}}cur++}Swap(&a[cur], &a[keyi]);return prev;
}
// 迭代过程
void QuickSort(int* a, int begin, int end)
{if(begin >= end) // 迭代的终点：左区间>=右区间时，迭代结束。return;int keyi = PartSort1(a, begin, end);//左：[begin,keyi -1] keyi 右：[keyi +1,end]QuickSort(a, begin, keyi -1); // 传参就是[0, n-1]QuickSort(a, keyi +1, end);
}

非递归法：递归最大问题是如果递归的太深，栈空间不够导致溢出，只能改成非递归
1.改循环—斐波那契
2.树遍历的非递归和快排非递归，只能用stack(栈)存储数据模逆递归
非递归法将数组区间一直入栈，分割后先入左边再入右边，这样栈可以每次先出右边再出左边，。直到分割的区间只有一个数或者没有数了这半边就不用入栈了。
栈里面存的是数组的下标。
在这里插入图片描述

// 实现支持动态增长的栈
typedef int STDataType;
typedef struct Stack
{STDataType* a;int top;       // 栈顶int capacity;  // 容量 
}Stack;// 初始化栈 
void StackInit(Stack* pst)
{assert(pst);pst->a = (STDataType*)malloc(sizeof(STDataType)*4);pst->top = 0;pst->capacity = 4;
}
// 销毁栈 
void StackDestroy(Stack* pst)
{assert(pst);free(pst->a);pst->a = NULL;pst->top = 0;pst->capacity = 0;
}
// 入栈 
void StackPush(Stack* pst, STDataType data)
{assert(pst);if(pst->top == pst->capacity){STDataType* tmp = (STDataType*)realloc(pst->a, sizeof(STDataType)*pst->capacity*2);if(tmp == NULL){printf("realloc fail\n");exit(-1); //结束掉整个程序}pst->a = tmp;pst->capacity *= 2;}pst->a[pst->top] = data;pst->top++;
}
// 出栈 
void StackPop(Stack* pst)
{assert(pst);assert(!StackEmpty(pst)); //如果栈已经空了就不要top--了pst->top--;
}
// 获取栈顶元素 
STDataType StackTop(Stack* pst)
{assert(pst);assert(!StackEmpty(pst)); //如果栈已经空了就不要top--了return pst->a[pst->top - 1];
}
// 检测栈是否为空，如果为空返回非零结果，如果不为空返回0 
int StackEmpty(Stack* pst)
{assert(pst);return pst->top == 0;
}
int StackSize(Stack* pst)
{assert(pst);return pst->top;
}// 快速排序 非递归实现
void QuickSortNonR(int* a, int left, int right)
{Stack st;StackInit(&st);//先入左再入右StackPush(&st, begin);StackPush(&st, end);while(!StackEmpty(&st)){int left, right;right = StackTop(&st);StackPop(&st);left = StackTop(&st);StackPop(&st);int keyi = PartSort1(a, left, right);if(left < keyi - 1) //如果左值小于keyi-1说明左边还有区间{StackPush(&st, left);StackPush(&st, keyi-1);}if(keyi+1 < right){StackPush(&st, keyi+1);StackPush(&st, right);}}StackDestory(&st);
}