快速排序

本文章的代码使用jetbrains公司旗下的的Clion编写，操作系统位macOS Ventura(13.2.1). 代码没有在dev-c++测试过（dev-c++可能会有相关的空格问题）
【对书上的内容进行了一点更新和优化，主要是对未知的特殊情况处理】

//
// Created by 魏志杰 on 2023/7/25.
//

#include "stdio.h"
#define Max 100
#define before  printf("排序前")
#define after   printf("排序后")
#define newline printf("\n")
#define print   printf("%6d", R[i].key)
#define printA  printf("%6d",A[i])
#define Array int A[]={5,7,2,5,9,6,-42,1,67,2,3};


typedef struct{
   int key;
   int data;
}SqType;



//从数列中挑出一个元素，称为 "基准"（pivot）;
//重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作；
//递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序;

//严蔚敏《数据结构》，标准分割函数

int partition(int A[], int low, int high) {
   int pivot = A[low];
   while (low < high) {
       while (low < high && A[high] >= pivot) {
           --high;
       }
       A[low] = A[high];
       while (low < high && A[low] <= pivot) {
           ++low;
       }
       A[high] = A[low];
   }
   A[low] = pivot;
   return low;
}

void quickSort(int A[], int low, int high) {
   if (low < high) {
       int pivot = partition(A, low, high);
       quickSort(A, low, pivot - 1);
       quickSort(A, pivot + 1, high);
   }
}

//李春葆
void quick(SqType R[], int s, int t) {
   int i = s, j = t;
   SqType tmp;
   if (s < t) {
       tmp = R[s];
       while (i != j) {
           while (j > i && R[j].key >= tmp.key)
               j--;
           if (i < j) {
               R[i] = R[j];
               i++;
           }
           while (i < j && R[i].key <= tmp.key)
               i++;
           if (i < j) {
               R[j] = R[i];
               j--;
           }
       }
       R[i] = tmp;
       quick(R, s, i - 1);
       quick(R, i + 1, t);
   }
}

void quick_1(SqType R[], int s, int t) {
   if (s >= t) { // 处理特殊情况：当 s >= t 时，不需要继续排序，直接返回
       return;
   }

   int i = s, j = t;
   SqType tmp = R[s]; // 将基准元素保存在临时变量 tmp 中
   while (i < j) {
       while (j > i && R[j].key >= tmp.key)
           j--;
       if (i < j) {
           R[i] = R[j];
           i++;
       }
       while (i < j && R[i].key <= tmp.key)
           i++;
       if (i < j) {
           R[j] = R[i];
           j--;
       }
   }
   R[i] = tmp;

   quick(R, s, i - 1); // 递归排序左半部分
   quick(R, i + 1, t); // 递归排序右半部分
}


int  main(){

   SqType R[Max];
   Array;
   for (int i = 0; i < 10; i++)
       R[i].key = A[i];
   before;
   for (int i = 0; i < 10; i++)
       print;
      newline;

   quick(R,0,9);
   after;
   for (int i = 0; i < 10; i++)
       print;
   newline;

   quick_1(R,0,9);
   after;
   for (int i = 0; i < 10; i++)
       print;
   newline;

   quickSort(A,0,9);
   after;
   for (int i = 0; i < 10; i++)
       printA;

}


}

结果如下