算法【快速排序】

算法【快速排序】

快速排序。选择一个作为比较的元素,这里我们选择首元素,这个元素我叫他‘比较元素’;前后两个指针(其实是索引变量)同时往后和往前进行遍历,开头的指针遇到比‘比较元素’大的元素停下来(空循环体的循环即可实现),末尾的指针往前遍历,遇到比‘比较元素’小的元素停下来;两个元素都停止后,交换两个元素,交换后通过外面的大循环继续让指针运动起来;当两个指针相遇或交错时,退出大循环;之后将从后面跑来的指针的元素与‘比较元素(首元素)’交换(因为这时这个从后面跑来的指针一定指向小于或等于首元素的元素),这样可以保证后面跑来的这个指针的位置元素,前面都是小于它的元素,后面都是大于它的元素;之后前面的进行递归,后面的也进行递归,递归的出口是开始的指针大于等于结束的指针(这个开始和结束的指针是上一个大的部分传来的)。

#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;
}

热门相关:傲娇总裁:蜜宠小甜妻!   仙碎虚空   傲娇驾到,总裁别闹   惊世第一妃   傲娇总裁:蜜宠小甜妻!