百度360必应搜狗淘宝本站头条
当前位置:网站首页 > 编程网 > 正文

十大经典排序算法之快速排序 快速排序的算法分析

yuyutoo 2024-10-12 01:08 5 浏览 0 评论

快速排序(Quick Sort)采用的是分治思想,即在一个无序的序列中选取一个任意的基准元素pivot,利用pivot将待排序的序列分成两部分,前面部分元素均小于或等于基准元素,后面部分均大于或等于基准元素,然后采用递归的方法分别对前后两部分重复上述操作,直到将无序序列排列成有序序列。

算法特性

  • 稳定性

快速排序是一种不稳定的排序算法。

  • 时间复杂度

快速排序的时间复杂度在最坏情况下是O(n^2),平均的时间复杂度是O(N*logN)。

  • 空间复杂度

快速排序是一种原地排序算法,不需要额外的空间进行排序。因此,快速排序的空间复杂度为O(1)。

算法步骤

快速排序算法通过多次比较和交换来实现排序,其流程如下:

1、首先设定一个基准值,通过该基准值将数组分成左右两部分。

2、将大于或等于基准值的数据集中到数组右边,小于基准值的数据集中到数组的左边。此时,左边部分中各元素都小于基准值,而右边部分中各元素都大于或等于基准值。

3、然后,左边和右边的数据可以独立排序。对于左侧的数组数据,又可以取一个基准值,将该部分数据分成左右两部分,同样在左边放置较小值,右边放置较大值。右侧的数组数据也可以做类似处理。

4、重复上述过程,可以看出,这是一个递归定义。通过递归将左侧部分排好序后,再递归排好右侧部分的顺序。当左、右两个部分各数据排序完成后,整个数组的排序也就完成了。

动画演示

代码实现

Java代码:

private static int[] quickSort(int[] array, int left, int right) {
    if (left < right) {
        int partitionIndex = partition(array, left, right);
        quickSort(array, left, partitionIndex - 1);
        quickSort(array, partitionIndex + 1, right);
    }

    return array;
}

private static int partition(int[] array, int left, int right) {
    // 设定基准值
    int pivot = left;
    int index = pivot + 1;
    for (int i = index; i <= right; i++) {
        if (array[i] < array[pivot]) {
            swap(array, i, index);
            index ++;
        }
    }

    swap(array, pivot, index - 1);

    return index - 1;
}

private static void swap(int[] array, int i, int j) {
    int temp = array[i];
    array[i] = array[j];
    array[j] = temp;
}

相关推荐

国内外注塑机及电脑密码大全(常见注塑机通用密码)

一、国外注塑机(日本、德国等)东洋注塑机万能码:9422345日精注塑机密码:222|7777DAMEG注塑机密码:000000000新泻注塑机密码:241650|261450住友注塑机密码:...

并发编程实战来咯(并发编程的艺术和并发编程实战)

提到并发编程,就不得不提C++ConcurrencyinAction(SecondEdition)(《C++并发编程实战第2版》)啦!《C++并发编程实战第2版》英文原版&中文译版看到这个...

无锁队列Disruptor原理解析(无锁队列应用场景)

队列比较队列...

理解 Memory barrier(内存屏障)(内存屏障 volatile)

...

并发编程 --- CAS原子操作(cas概念、原子类实现原理)

...

无锁CAS(附无锁队列的实现)(cas是一种无锁算法)

本文所有代码对应的Github链接为:https://github.com/dongyusheng/csdn-code/tree/master/cas_queue...

Linux高性能服务器设计(linux 服务器性能)

C10K和C10M计算机领域的很多技术都是需求推动的,上世纪90年代,由于互联网的飞速发展,网络服务器无法支撑快速增长的用户规模。1999年,DanKegel提出了著名的C10问题:一台服务器上同时...

浅谈Go语言的并发控制(go语言 并发)

前言本文原创,著作权归...

Datenlord |Etcd 客户端缓存实践(etcd 数据存储)

简介和背景...

无锁编程——从CPU缓存一致性讲到内存模型

缓存是一个非常常用的工程优化手段,其核心在于提升数据访问的效率。缓存思想基于局部性原理,这个原理包括时间局部性和空间局部性两部分:...

打通 JAVA 与内核系列之 一 ReentrantLock 锁的实现原理

...

如何利用CAS技术实现无锁队列(cas会锁总线吗)

linux服务器开发相关视频解析:...

Kotlin协程之一文看懂Channel管道

概述Channel类似于Java的BlockingQueue阻塞队列,不同之处在于Channel提供了挂起的send()和receive()方法。另外,通道Channel可以...

详解C++高性能无锁队列的原理与实现

1.无锁队列原理1.1.队列操作模型...

Javascript 多线程编程的前世今生

...

取消回复欢迎 发表评论: