算法【快速排序】
算法【快速排序】
快速排序。选择一个作为比较的元素，这里我们选择首元素，这个元素我叫他‘比较元素’；前后两个指针（其实是索引变量）同时往后和往前进行遍历，开头的指针遇到比‘比较元素’大的元素停下来（空循环体的循环即可实现），末尾的指针往前遍历，遇到比‘比较元素’小的元素停下来；两个元素都停止后，交换两个元素，交换后通过外面的大循环继续让指针运动起来；当两个指针相遇或交错时，退出大循环；之后将从后面跑来的指针的元素与‘比较元素（首元素）’交换（因为这时这个从后面跑来的指针一定指向小于或等于首元素的元素），这样可以保证后面跑来的这个指针的位置元素，前面都是小于它的元素，后面都是大于它的元素；之后前面的进行递归，后面的也进行递归，递归的出口是开始的指针大于等于结束的指针（这个开始和结束的指针是上一个大的部分传来的）。
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define N 10
/**
* 快排
*/
void quick_sort(int *arr, int size);
void recursion(int *arr, int start, int end);
// 快排
void quick_sort(int *arr, int size){
recursion(arr, 0, size-1);
}
// 快排的递归逻辑
void recursion(int *arr, int start, int end){
// 第一个作为比较的元素
int comElement = arr[start];
// 后面首元素的下标和尾元素的下标都要改变，现在先记录一下。
int start_temp = start;
int end_temp = end;
if(start_temp <= end_temp){
while(1){
// 移动前后两个下标
while(start<=end_temp && comElement > arr[++start]); // 前下标没有移动到最后且该位置元素大于比较元素时持续后移。即前下标超过末尾或元素大于等于比较元素时停止后移
while(end >=start_temp && comElement < arr[end--]); // 后元素小于起始元素 或 该位置元素小于等于比较元素时停止后移
end++; // 将最后往前移多的下标加上。
if(start >= end) break; // 后位置大于前位置，不进行交换
// 这里不能使用异或 或者 相加 的方式交换， 因为可能操作的是同一个元素。
int temp = arr[start];
arr[start] = arr[end];
arr[end] = temp;
}
int temp = arr[start_temp];
arr[start_temp] = arr[end];
arr[end] = temp;
static int x_20231217 = 1;
printf("第%d趟排序结果为：\t", x_20231217++);
for(int i = 0; i<N; i++) printf("%d\t", arr[i]);
printf("\n");
// 递归
recursion(arr, start_temp,end-1); // end 的位置是之前 比较元素 的那个位置
recursion(arr, end+1, end_temp);
}
}
int main(int argc, char const *argv[]){
// 生成随机种子
srand(time(0));
int arr[N];
for(int i = 0; i<N; i++) arr[i] = rand()%10 + 1;
printf("原始数据为：\t\t");
// 打印原始数据
for(int i = 0; i<N; i++) printf("%d\t", arr[i]);
printf("\n");
// 调用快速排序
quick_sort(arr, N);
printf("最终数据为：\t\t");
// 打印排序后的数据
for(int i = 0; i<N; i++) printf("%d\t", arr[i]);
printf("\n");
getchar();
return 0;
}