【数据结构与算法篇】手撕八大排序算法之快排的非递归实现及递归版本优化(三路划分)

void Swap(int* a, int* b)
{
  int tmp = *a;
  *a = *b;
  *b = tmp;
}
//hoare版本
int Partition1(int* a, int left, int right)
{
  int keyi = left;
  while (left < right)
  {
    //注意： 要加上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[left], &a[keyi]);
  return left;
}
void QuicksortNonR(int* a, int begin, int end)
{
  Stack st;
  StackInit(&st);
  //注意栈的顺序是后进先出，需要倒着放进去，正着拿出来
  //将排序数组的起始和末端下标入栈
  StackPush(&st, end);
  StackPush(&st, begin);
  //栈不为空一直循环
  while (!StackEmpty(&st))
  {
    //弹出子区间(左右两个下标)
    int left = StackTop(&st);
    StackPop(&st);
    int right = StackTop(&st);
    StackPop(&st);
    //执行分区操作
    int keyi = Partition1(a, left, right);
    //[left,keyi - 1] keyi [keyi + 1, right]
    //注意只剩一个数或区间不存在则停止入栈
    if (keyi + 1 < right)
    {
      StackPush(&st,right);
      StackPush(&st,keyi + 1);
    }
    if (left < keyi - 1)
    {
      StackPush(&st, keyi - 1);
      StackPush(&st, left);
    }
  }
}
void PrintArray(int* a, int n)
{
  for (int i = 0; i < n; i++)
  {
    printf("%d ", a[i]);
  }
}
int main()
{
  int a[] = { 9,6,7,1,4,5,5,2,10,1,6,3,7 };
  QuicksortNonR(a, 0, sizeof a / sizeof(int) - 1);
  PrintArray(a, sizeof a / sizeof(int));
}

#pragma once
#include <stdio.h>
#include <stdbool.h>
#include <assert.h>
#include <stdlib.h>
typedef int DataType;
typedef struct Stack
{
  DataType* a;
  int top;
  int capacity;
}Stack;
//栈的初始化
void StackInit(Stack* pst);
//入栈
void StackPush(Stack* pst,DataType x);
//出栈
void StackPop(Stack* pst);
//栈的销毁
bool StackEmpty(Stack* pst);
//获取栈顶元素
DataType StackTop(Stack* pst);
//获取栈元素个数
int StackSize(Stack* pst);
//栈的销毁
void StackDestroy(Stack* pst);

#define  _CRT_SECURE_NO_WARNINGS 
#include "stack.h"
//栈的初始化
void StackInit(Stack* pst)
{
  assert(pst);
  pst->a = NULL;
  //pst->top = -1;//栈顶元素的位置
  pst->top = 0;//栈顶元素的下一个位置
  pst->capacity = 0;
}
//入栈
void StackPush(Stack* pst,DataType x)
{
  if (pst->top == pst->capacity)
  {
    int newCapacity = pst->capacity == 0 ? 4 : (pst->capacity) * 2;
    DataType* tmp = (DataType*)realloc(pst->a, sizeof(DataType) * newCapacity);
    if (tmp == NULL)
    {
      perror("realloc fail\n");
      return;
    }
    else
    {
      pst->a = tmp;
      pst->capacity = newCapacity;
    }
  }
  pst->a[pst->top++] = x;
}
//出栈
void StackPop(Stack* pst)
{
  assert(pst);
  pst->top--;
}
//判断栈是否为空
bool StackEmpty(Stack* pst)
{
  assert(pst);
  return pst->top == 0;
}
//获取栈顶元素
DataType StackTop(Stack* pst)
{
  return pst->a[pst->top - 1];
}
//获取栈元素个数
int StackSize(Stack* pst)
{
  return pst->top;
}
//栈的销毁
void StackDestroy(Stack* pst)
{
  assert(pst);
  free(pst->a);
  pst->a = NULL;
  pst->top = pst->capacity = 0;
}

/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
void Swap(int* p1, int* p2)
{
  int tmp = *p1;
  *p1 = *p2;
  *p2 = tmp;
}
//三数取中
int GetMidIndax(int* a,int left, int right)
{
    int mid = left + (rand() % (right - left));
    if (a[mid] > a[left])
    {
      if (a[right] > a[mid])  return mid;
      else if (a[right] > a[left]) return right;
      else return left;
    }
    else //a[mid] < a[left]
    {
      if (a[right] < a[mid]) return mid;
      else if (a[right] < a[left]) return right;
      else return left;
    }
}
 //hoare版本
int Partition1(int* a, int left, int right)
{
    int midi = GetMidIndax(a, left, right);
    Swap(&a[left],&a[midi]);
    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[left], &a[keyi]);
  return left;
}
 //快排(递归版本)
void QuickSort(int* a, int begin, int end)
{
  if (begin >= end) return;
  int keyi = Partition1(a, begin, end);
  //前序遍历
  //递归基准值左边的区间
  QuickSort(a, begin, keyi - 1);
  //递归基准值右边的区间
  QuickSort(a, keyi + 1, end);
}
int* sortArray(int* nums, int numsSize, int* returnSize){
    QuickSort(nums, 0, numsSize - 1);
    *returnSize = numsSize;
    return nums;
}

/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
void Swap(int* p1, int* p2)
{
  int tmp = *p1;
  *p1 = *p2;
  *p2 = tmp;
}
int GetMidIndax(int* a,int left, int right)
{
  int mid = left + (rand() % (right - left));
  if (a[mid] > a[left])
  {
    if (a[right] > a[mid])  return mid;
    else if (a[right] > a[left]) return right;
    else return left;
  }
  else //a[mid] < a[left]
  {
    if (a[right] < a[mid]) return mid;
    else if (a[right] < a[left]) return right;
    else return left;
  }
}
//三路分割 左 l r 右
void QuickSort(int* a, int begin, int end)
{
  if (begin >= end) return;
  int left = begin;
  int right = end;
  int cur = left + 1;
    int mid = GetMidIndax(a, begin, end);
    Swap(&a[mid],&a[left]);
  int key = a[left];
  while (cur <= right)
  {
    if (a[cur] < key)
    {
      Swap(&a[cur], &a[left]);
      left++;
      cur++;
    }
    else if (a[cur] > key)
    {
      Swap(&a[cur], &a[right]);
      right--;
    }
    else //a[cur] == key
    {
      cur++;
    }
  }
  // [begin left- 1],[left,right],[right + 1,end]
  QuickSort(a, begin, left - 1);
  QuickSort(a, right + 1, end);
}
int* sortArray(int* nums, int numsSize, int* returnSize){
    srand(time(NULL));
    QuickSort(nums, 0, numsSize - 1);
    *returnSize = numsSize;
    return nums;
}