快速排序-递归/分治法(C/Java/Python)(2021/3/21更新)

算法目录

2021/3/21更新:代码打错了…还缺了等号…补上了…等后面我多做一点排序题,再来更新点有用的。

算法介绍

快速排序是一种排序算法,时间复杂度为O(N*logN)。

算法思想

  1. 选择参考点。
  2. 比参考点大的数放参考点右边,小的则放左边。
  3. 以参考点为边界,再对两边进行快速排序

步骤过程

本文章介绍的是使用递归的,参考点取左边界的快速排序。
后续我会写个用栈实现的非递归,一定会写,一定。一定。
然后会把分类和标签再加上数据结构。

一次排序的搜索过程,是左右边界的两个指针,向中间移动,
一旦两个指针指向同一个地方,那么本次排序就结束了,参考点的位置就标定了,
可以看下面的示例,第一次排序结束后,参考值3就找到所在位置。

在排序的过程中,
先将参考点与右指针比较,如果是正序的,就将右指针左移,
如果出现逆序,即参考值>右指针,那么将此时的左指针的值设置为右指针的值,
然后对比左指针,正序跳过,直到逆序,
将右指针的值设置成做指针的值,
之后比较右指针、左指针、右指针…

这里不是很好理解,为什么比对参考点与右指针比较,却修改了左指针的值,
拿张草稿纸出来动手试一下,会更容易记一点,
或者看下面的示例。

排序示例

arr表示array[]数组,为待分配数组,
r表示compareRight,为比较用的右指针,
l表示compareLeft,为比较用的左指针,
sta表示standard,为参考点的值。

待排序数组

34152

第一次排序
(左侧数组为右侧代码执行后结果)

34152开始排序
24152arr[r]<sta, arr[l]=arr[r]
24152arr[l]<sta, l++
24154arr[l]>sta, arr[r]=arr[l]
24154arr[r]>sta, r–
24154arr[r]>sta, r–
21154arr[r[<sta, arr[l]=arr[r]
21154arr[l]<sta, l++
21354l == r, arr[l]=sta

第二次排序
对第一次排序结果的左边排序

21开始排序
11arr[r]<sta, arr[l]=arr[r]
11arr[l]<sta, l++
12l == r, arr[l]=sta

第三次排序
对第一次排序结果的右边排序

54开始排序
44arr[r]<sta, arr[l]=arr[r]
44arr[l]<sta, l++
45l == r, arr[l]=sta

排序后数组

12345

C版本代码

void quickSoft(int *array, int left, int right){
	if (left>right) return;		 
	int compareLeft = left;
	int compareRight = right;
	int standard = array[compareLeft];
	while(compareLeft<compareRight){
		while(compareLeft<compareRight && standard<=array[compareRight]) 
			compareRight -= 1;
		if(compareLeft<compareRight)
			array[compareLeft] = array[compareRight];
		while(compareLeft<compareRight && standard>=array[compareLeft])
			compareLeft += 1;
		if(compareLeft<compareRight)
			array[compareRight] = array[compareLeft];
	}
	array[compareLeft] = standard;
	quickSoft(array, left, compareLeft-1);
	quickSoft(array, compareLeft+1, right);
}

Java版本代码

static int getStandard(int []array, int leftPos, int rightPos){
		int standard = array[leftPos];
		while(leftPos<rightPos){
			while(leftPos<rightPos && standard<=array[rightPos])
				rightPos -= 1;
			if(leftPos<rightPos)
				array[leftPos] = array[rightPos];
			while(leftPos<rightPos && standard>=array[leftPos])
				leftPos += 1;
			if(leftPos<rightPos)
				array[rightPos] = array[leftPos];
		}
		array[leftPos] = standard;
		return leftPos;
	}

	static void quickSoft(int []array, int leftPos, int rightPos){
		if(leftPos<rightPos){
			int standardPos = getStandard(array, leftPos, rightPos);
			quickSoft(array, leftPos, standardPos-1);
			quickSoft(array, standardPos+1, rightPos);
		}
	}

Python版本代码

def quickSoft(array, left, right):
    if left>right:
        return
    compareLeft = left
    compareRight = right
    standard = array[compareLeft]
    while compareLeft<compareRight:
        while compareLeft<compareRight and standard<=array[compareRight]:
            compareRight -= 1
        if compareLeft<compareRight:
            array[compareLeft] = array[compareRight]
        while compareLeft<compareRight and standard>=array[compareLeft]:
            compareLeft += 1
        if compareLeft<compareRight:
            array[compareRight] = array[compareLeft]
    array[compareLeft] = standard
    quickSoft(array, left, compareLeft-1)
    quickSoft(array, compareLeft+1, right)

You may also like...

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注