快速排序（c++）——经典交换排序（二）

news/2025/2/26 3:19:05

快速排序——经典交换排序（二）

算法原理：

快速排序采用分治法
在待排序序列中任选一个元素pivot作为基准（一般取首元素）
通过一趟排序将待排序的序列划分为两部分
将数组中小于基准数的数据移到基准数左边，大于基准数的移到右边

详细图解：

1.设置两个指针i,j分别指向最左边left和最右边right
2.设置第一个数为基准数 temp = arr[left];
3. j指针先从右往左移动，如果 arr[j] >= temp 即大于基准值j–,（因为要找小于基准值的）当 arr[j] < temp 时找到一个小于基准值,此时将该值与基准值交换（ arr[i] = arr[j]; ）
3.i指针先从左往右移动，如果 arr[i] <= temp 即小于基准值i++,（因为要找大于基准值的）当 arr[i] > temp 时找到一个大于基准值,此时将该值与基准值交换（ arr[j] = arr[i]; ）
4.直接 i >= j,此时一趟排序结束，将基准值归位arr[i] = temp;
5.依次对两个子表进行递归排序（重复以上步骤）
quicksort(arr, left, i - 1);
quicksort(arr, i + 1, right);

C++代码：

//快速排序函数算法
void quicksort(int *arr, int left, int right) {
	int i, j, temp;
	if (left > right) {
		return;
	}
	//基准
	i = left;
	j = right;
	while (i < j) {
		while (arr[j] >= temp && i < j) {    //找出右边小于基准值的数放到左边
			j --;
		}
		arr[i] = arr[j];                     //交换
		while (arr[i] <= temp && i < j) {    //找出左边大于基准值的数放到右边
			i ++;
		}
		arr[j] = arr[i];
	}
	//归位
	arr[i] = temp;
	quicksort(arr, left, i - 1);
	quicksort(arr, i + 1, right);
}