快速排序算法

时间:2022-12-14 09:49:12

--快速排序算法

算法思想:基于分治的思想,是冒泡排序的改进型。首先在数组中选择一个基准点,一般选择数组的第一个元素,然后分别从数组的两端扫描数组,设两个指示标志(start指向起始位置,end指向末尾),首先从后半部分开始,如果发现有元素比该基准点的值小,就交换start和end位置的值,然后从前半部分开始扫秒,发现有元素大于基准点的值,就交换start和end位置的值,一次排序就完成了。结束第一次循环时,对于基准点来说,它左边的数都小于他,右边的数多大于它。然后采用递归的方式在一准基点的左右两边重复上述的这个数组里的数就可以变成有序的了。

快速排序算法

以下时实现的代码

public class test {

	public static void operation(int[] array, int min, int max) {
		int start = min;
		int end = max;
		int key = array[min];
		while (end > start) {
			// 从后面开始开始找比基准值小的数
			while (end > start && array[end] >= key) {
				// 如果没有比基准值小的,比较下一个,直到有比关键值小的交换位置,然后又从前往后比较
				end--;
			}
			//值的交换
			if (array[end] <= key) {
				int index = array[end];
				array[end] = array[start];
				array[start] = index;
			}
			// 从前面开始开始找比基准值大的数
			while (end > start && array[start] <= key) {
				//如果没有比关键值大的,比较下一个,直到有比关键值大的交换位置
				start++;
			}
			//值的交换
			if (array[start] >= key) {
				int index = array[start];
				array[start] = array[end];
				array[end] = index;
			}
		}
		  //递归
		if (start > min) {
			//左边序列。第一个索引位置到基准值的索引-1
			operation(array, min, start - 1);
		}
		if (end < max) {
			//右边序列。从基准值的索引+1到最后一个
			operation(array, end + 1, max);
		}
	}

	public static void main(String[] args) {
		int[] array = { 11, 5, 6, 45, 16, 15, 34, 66, 1, 1 };
		operation(array, 0, array.length - 1);
		for (int i = 0; i < array.length; i++) {
			System.out.println(array[i]);
		}
	}
}

结果

快速排序算法