【六大排序详解】终篇 :冒泡排序 与 快速排序

void BubbleSort(int* a, int n)
 {
  for (int i = 0; i < n; i++) //从头开始遍历
  {
       //每次遍历 会排完一个 需排序部分减少 1 
    for (int j = 0; j < n - 1 - i;j++) 
    {   //结束条件 a[n-2] > a[n-1]
      if (a[j] > a[j + 1]) //如果大，向上冒
      {      
        int tmp = a[j];
        a[j] = a[j + 1];
        a[j + 1] = tmp;
      }
    }
  }
}

//交换函数
void Swap(int* p1, int* p2) {
  int tmp = *p1;
  *p1 = *p2;
  *p2 = tmp;
}
//key 取中位数
int getmidi(int *a,int begin,int end) {
  int midi = (begin + end) / 2;
  if (a[midi] > a[begin]) {
    if (a[midi] < a[end]) return midi;
    else if (a[begin] > a[end]) return begin;
    else return end;
  }
  else {//a[midi]<a[begin]
    if (a[begin] < a[end])  return begin;
    else if (a[midi] > a[end]) return midi;
    else return end;
}

//Hoare版本快速排序
int PartSort1(int* a, int left, int right) {
  //取key 为首元素
  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]);
  }
  //将key与相遇位置值交换，
  //满足左边都比key小，右边都比key大
  Swap(&a[keyi], &a[left]);
  keyi = left;
}
//快速排序主体
void QuickSort(int* a, int begin, int end) {
  //递归实现
  if (begin >= end) return;
    // 定义左边，右边与key相应位置。
  int left = begin, right = end ;
  int keyi = begin;
  //该步骤优化十分重要。
  int midi = getmidi(a, begin, end);
  Swap(&a[left], &a[midi]);
  //排序
  int key = PartSort1(a, left, right);

  QuickSort(a, begin, key-1);
  QuickSort(a, key+1, end);
}

int PartSort2(int* a, int left, int right) {
  int key = a[left]; //key取左值
  int holei = left;
    //开始排序
  while(left < right){
        //右找大
    while (a[right] >= key && right > left) {
      right--;
    }
        //进坑 挖坑
    a[holei] = a[right];
    holei = right;
        //左找小
    while (a[left] <= key && right > left) {
      left++;
    }
        //进坑 挖坑   
        a[holei] = a[left];
    holei = left;
  }
    //结束时，key进坑。完成排序
  a[holei] = key;
  return left;
}

void Swap(int* p1, int* p2) {
  int tmp = *p1;
  *p1 = *p2;
  *p2 = tmp;
}
int PartSort3(int* a, int begin, int end) {
  int key = a[begin];
  int prev = begin, cur = prev + 1;

  while (cur <= end) {
    if (a[cur] < key) {
      prev++;
      if (prev != cur)
        Swap(&a[cur], &a[prev]);
    }
    cur++;
  }
  Swap(&a[begin], &a[prev]);
  return prev;
}

//非递归排序
void QuickSortNonR(int* a, int begin, int end) {
  //建立栈
  Stack s ;
  StackInit(&s);//初始化
  //压入开始与结束位置
  StackPush(&s, begin);
  StackPush(&s, end);
    //开始排序
  while (!StackEmpty(&s)) {//不为空就继续进行
      //出栈读入右位置
    int right = StackTop(&s);
    //读取后删除
    StackPop(&s);
    //出栈读入左位置
    int left = StackTop(&s);
    //读取后删除
    StackPop(&s);
        //对该部分进行排序 这里使用前后指针法（使用三种其一即可）
    int keyi = PartSort3(a, left, right);
        //读取左部分 若left>=key不进行读入
    if (left < keyi) {
       //入栈 
      StackPush(&s, left);
      StackPush(&s, keyi - 1);
    }
        //读取右部分 若right<=key不进行读入
    if (right > keyi) {
       //入栈
      StackPush(&s, keyi + 1);
      StackPush(&s, right);
    }   
  }
}