前言
一種將無(wú)序數(shù)組進(jìn)行排序的方法斜筐。
快速排序,參雜了冒泡排序的交換思想屠列。
wiki參考:
https://zh.wikipedia.org/wiki/%E5%BF%AB%E9%80%9F%E6%8E%92%E5%BA%8F
本文只提及了遞歸方式的實(shí)現(xiàn),該算法整體類似于二叉樹(shù)踪央,普通的迭代方法反而更加復(fù)雜。
環(huán)境
編輯器:vs2019
文件:.c類型
正文
代碼參考:
#include <stdio.h>
// 快速排序瓢阴,主要思想:1. 取基值畅蹂。2. 分割(基值左小右大)
void swap(int* x, int* y) {
int t = *x;
*x = *y;
*y = t;
}
// start: 起始索引
// end: 結(jié)束索引
void quick_sort_recursive(int source_array[], int start, int end)
{
if (start >= end)
{
return 0;
}
// 取基值
// source_array[end];
// 確定分割數(shù)組的索引
int left = start;
int right = end - 1;
// 開(kāi)始分割
while (left < right)
{
// 從左向右找到比基值大的數(shù)
while (source_array[left] < source_array[end])
{
left++;
}
// 從右向左找到比基值小的數(shù)
while (source_array[right] > source_array[end])
{
right--;
}
// 交換兩個(gè)元素
if (left < right)
{
swap(&source_array[left], &source_array[right]);
left++;
right--;
}
}
// 最后移動(dòng)基值。循環(huán)結(jié)束以后荣恐,left指向 從左向右,第一個(gè)大于等于基值的值
if (left < end)
{
swap(&source_array[left], &source_array[end]);
}
quick_sort_recursive(source_array, start, left - 1);
quick_sort_recursive(source_array, left + 1, end);
}
int main()
{
// 生成隨機(jī)測(cè)試列表
int test_list[30];
int test_list_length = sizeof(test_list) / sizeof(int);
printf("測(cè)試列表: \n");
for (int i = 0; i < test_list_length; i++)
{
test_list[i] = rand() % 100;
printf("%d ", test_list[i]);
}
printf("\n");
// 遞歸快速排序
quick_sort_recursive(test_list, 0, test_list_length - 1);
printf("遞歸快速排序結(jié)果: \n");
for (int i = 0; i < test_list_length; i++)
{
printf("%d ", test_list[i]);
}
printf("\n");
return 0;
}
執(zhí)行結(jié)果參考:
image.png