快速排序

快速排序思想

快速排序采用的思想是分治思想。

快速排序是找出一个元素(理论上可以随便找一个)作为基准(pivot),然后对数组进行分区操作,使基准左边元素的值都不大于基准值,基准右边的元素值 都不小于基准值,如此作为基准的元素调整到排序后的正确位置。递归快速排序,将其他n-1个元素也调整到排序后的正确位置。最后每个元素都是在排序后的正 确位置,排序完成。所以快速排序算法的核心算法是分区操作,即如何调整基准的位置以及调整返回基准的最终位置以便分治递归。

算法步骤:

1.分解:

A[p..r]被划分为俩个(可能空)的子数组A[p ..q-1]和A[q+1 ..r],使得 A[p ..q-1] <= A[q] <= A[q+1 ..r]

2.解决:通过递归调用快速排序,对子数组A[p ..q-1]和A[q+1 ..r]排序。

3.合并。

排序

基准(pivot)的选取选取数组分区后的第一个元素 对数组a[i,...,j]进行操作: 1.首先选择一个中间元素(一般选左端或者右端)。

2.分别获取除中间元素外的左右两端的索引。

3.由左右两端逐渐向中间迭代,每迭代一步比较一下索引中的元素和中间元素,当左边出现比中间元素大的元素的时候,暂停左边的迭代,当右边迭代出比中间元素小的元素的时候,右边迭代也暂停,交换左右两边的元素。

4.重复步骤3,直到左右两边的索引相遇,然后将中间元素移动到中间,这时中间元素左边的元素都比它小,右边的元素都比它大。

5.将上面的中间元素左右两边当成两个数组,分别进行上述过程。

6.重复以上步骤直到数组不可再分。

代码如下

public class quick_sort {

    /**
     * @param args
     */
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        int[] a={4,5,6,7,223,21,5,22,445,55,2,5,88,33,66,22,4456,3,24,56,78,222};
        quickSort(a);
        for(int i=0;i<a.length;i++){
            System.out.println(a);
        }

    }
    public static void sort(int array[],int low,int high){
        int i,j;
        int index;
        if(low>=high){
            return;
        }
        i=low;
        j=high;
        index=array[i];
        while(i<j){
            while(i<j && array[j]>=index){
                j--;
                
            }
        if(i<j){
            array[i++]=array[j];
            
        }
        while(i<j && array[i]<index){
            
        }
        if(i<j){
            array[j--]=array[i];
        }
            
        }
        array[i]=index;
        sort(array,low,i-1);
        sort(array,i+1,high);
    }
    public static void quickSort(int array[]){
        sort(array,0,array.length-1);
    }

}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏数据结构与算法

cf314E. Sereja and Squares(dp)

给你一个擦去了部分左括号和全部右括号的括号序列,括号有25种,用除x之外的小写字母a~z表示。求有多少种合法的括号序列。答案对4294967296取模。 合法序...

1527
来自专栏抠抠空间

算法基础

1134
来自专栏Python小屋

Python模拟大整数乘法的小学竖式计算过程

让我们先看个图回顾一下小学学过的计算整数乘法的竖式计算过程 ? 然后再来看如何使用Python来模拟上面的过程,虽然在Python中计算任意大的数字乘法都没有问...

3345
来自专栏python3

习题4:变量和命名

"_"下划线这个符号在变量里通常被用作假象的空格,用来隔开单词,切记千万不要用"-"这个符号来连接单词

562
来自专栏IT可乐

深入理解计算机系统(2.6)------整数的运算

  前面两篇博客我们详细讲解了计算机中整数的表示,包括有符号和无符号(补码编码)的详细介绍。那么这篇博客我们将对它们的运算有个详细的了解。   在讲解之前首先看...

2597
来自专栏开发与安全

从零开始学C++之STL(四):算法简介、7种算法分类

一、算法 算法是以函数模板的形式实现的。常用的算法涉及到比较、交换、查找、搜索、复制、修改、移除、反转、排序、合并等等。 算法并非容器类型的成员函数,而是一...

2040
来自专栏Golang语言社区

深入解析快速排序算法的原理及其Go语言版实现

快速排序是一种基于分治技术的重要排序算法。不像归并排序是按照元素在数组中的位置对它们进行划分,快速排序按照元素的值对它们进行划分。具体来说,它对给定数组中的元素...

3385
来自专栏CDA数据分析师

学会这8个(组)excel函数,轻松解决工作中80%的难题

文 | 兰色幻想-赵志东 函数是excel中最重要的分析工具,面对400多个excel函数新手应该从哪里入手呢?下面是实际工作中最常用的8个(组)函数,学会后工...

1947
来自专栏编程之旅

唠唠快速排序算法

每一个从事计算机相关方向工作的同学一定听说过快速排序算法,在面试的准备过程中,快排也一定是一个必须要牢牢掌握的算法。那么今天就来唠唠快速排序算法。

1042
来自专栏算法channel

直接选择排序到堆排序做的那些改进

主要推送关于对算法的思考以及应用的消息。坚信学会如何思考一个算法比单纯地掌握100个知识点重要100倍。本着严谨和准确的态度,目标是撰写实用和启发性的文章,欢迎...

2957

扫码关注云+社区

领取腾讯云代金券