算法 - 排序之快速排序

本贴最后更新于 1545 天前,其中的信息可能已经时移世改

概述

快速排序采用了分治策略。就是在一个数组中取一个基准数字,把小的数放基准的左边,大的数放基准的右边。 基准左边和右边分别是新的序列。在新的序列中再取一个基准数字,小的放左边,大的放右边。

动图演示

图片来源:百度
algorithmquickSort.gif

优缺点

优点

极快,数据移动少

缺点

不稳定

复杂度

时间

  1. 最好情况:O(nlog2(n))
  2. 平均情况:O(nlog2(n))
  3. 最坏情况:O(n^2)

空间

O(log2(n))

使用场景

适用于数组长度比较大的情况,对于小数组,快速排序比插入排序慢

代码


import java.util.Arrays;

/**
 * ===============================
 * 作者:amos lam
 * 时间:2020年1月5日下午12:37:50
 * 备注:算法 - 排序之快速排序
 * ===============================
 */
public class QuickSort {

	public static void main(String[] args) {

		int[] arr = new int[] { 32, 26, 83, 55, 42, 67, 73, 92, 60 };
		quickSort(arr, 0, arr.length - 1);
		System.out.println(Arrays.toString(arr));
	}

	public static void quickSort(int[] arr, int low, int high) {
		
		if (low < high) {
			
			int temp = quickPartition(arr, low, high);
			quickSort(arr, low, temp - 1);
			quickSort(arr, temp + 1, high);
		}
	}

	public static int quickPartition(int[] arr, int low, int high) {
		
		int key = arr[low];
		while (low < high) {
			
			while (low < high && arr[high] >= key) {
				
				high--;
			}
			arr[low] = arr[high];
			while (low < high && arr[low] <= key) {
				
				low++;
			}
			arr[high] = arr[low];
		}
		arr[low] = key;
		return low;
	}
}
  • 算法
    388 引用 • 254 回帖 • 22 关注
  • Java

    Java 是一种可以撰写跨平台应用软件的面向对象的程序设计语言,是由 Sun Microsystems 公司于 1995 年 5 月推出的。Java 技术具有卓越的通用性、高效性、平台移植性和安全性。

    3165 引用 • 8206 回帖

相关帖子

欢迎来到这里!

我们正在构建一个小众社区,大家在这里相互信任,以平等 • 自由 • 奔放的价值观进行分享交流。最终,希望大家能够找到与自己志同道合的伙伴,共同成长。

注册 关于
请输入回帖内容 ...