快速排序是找出一个元素(理论上可以随便找一个)作为基准(pivot),然后对数组进行分区操作,使基准左边元素的值都不大于基准值,基准右边的元素值 都不小于基准值,如此作为基准的元素调整到排序后的正确位置。递归快速排序,将其他n-1个元素也调整到排序后的正确位置。最后每个元素都是在排序后的正 确位置,排序完成。所以快速排序算法的核心算法是分区操作,即如何调整基准的位置以及调整返回基准的最终位置以便分治递归。
一趟快速排序的算法是:
1)设置两个变量i、j,排序开始的时候:i=0,j=N-1;
2)以第一个数组元素作为关键数据,赋值给key,即key=A[0];
3)从j开始向前搜索,即由后开始向前搜索(j--),找到第一个小于key的值A[j],将A[j]和A[i]互换;
4)从i开始向后搜索,即由前开始向后搜索(i++),找到第一个大于key的A[i],将A[i]和A[j]互换;
5)重复第3、4步,直到i=j; (3,4步中,没找到符合条件的值,即3中A[j]不小于key,4中A[i]不大于key的时候改变j、i的值,使得j=j-1,i=i+1,直至找到为止。找到符合条件的值,进行交换的时候i, j指针位置不变。另外,i==j这一过程一定正好是i+或j-完成的时候,此时令循环结束)。
举例说明一下吧,这个可能不是太好理解。假设要排序的序列为
package com.zc.manythread; import java.util.Random; /** * 快速排序 * @author Administrator * */ public class QSort { int [] date; public QSort(int[] date) { this.date=date; } /** * 交换函数 * @param a * @param i * @param j */ private void swap(int a[],int i,int j) { int T; T=a[i]; a[i]=a[j]; a[j]=T; } /******************* * 排序函数 * @param a * @param lo0 * @param hi0 * @return */ int[] QuickSort(int a[],int lo0,int hi0){//分治法,作用就是将数组分为A[lo0..q-1] 和A[q+1..hi0] int lo=lo0; int hi=hi0; int mid; if (hi0>lo0) { mid=a[(hi0+lo0)/2]; while(lo<=hi){ while((lo<hi0)&&(a[lo]<mid)) ++lo; while((hi>lo0)&&(a[hi]>mid)) --hi; if (lo<=hi) { swap(a,lo,hi); ++lo; --hi; } } if (lo0<hi) { QuickSort(a, lo0, hi); } if (lo<hi0) { QuickSort(a, lo, hi0); } } return a; } /************** * * 创建有重复数组数据 * *****************/ private static int[] createDate(int count) { int[] data=new int[count]; for (int i = 0; i < data.length; i++) { data[i]=(int)(Math.random()*count); } return data; } /** * 无重复数组数据 * @param count * @return */ private static int[] createDate1(int count) { int[] data=new int[count]; Random rand = new Random(); boolean[] bool = new boolean[100]; int num = 0; for (int i = 0; i < count; i++) { do { // 如果产生的数相同继续循环 num = rand.nextInt(100); } while (bool[num]); bool[num] = true; data[i]=num; } return data; } /**************主函数*****************/ public static void main(String[] args) { final int count=10; int[] data=createDate1(count); for (int n:data) { System.out.print(n+"\t"); } QSort data1=new QSort(data); System.out.println(); int[] a=data1.QuickSort(data,0, count-1); for (int n:a) { System.out.print(n+"\t"); } } }
结果如下:
以上就是本文所述的全部内容了,希望小伙伴们能够喜欢。
本文向大家介绍C#排序算法之快速排序解析,包括了C#排序算法之快速排序解析的使用技巧和注意事项,需要的朋友参考一下 本文实例为大家分享了C#实现快速排序的具体代码,供大家参考,具体内容如下 代码: 以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持呐喊教程。
主要内容:快速排序算法的实现提到排序算法,多数人最先想到的就是快速排序算法。快速排序算法是在分治算法基础上设计出来的一种排序算法,和其它排序算法相比,快速排序算法具有效率高、耗费资源少、容易实现等优点。 快速排序算法的实现思路是: 从待排序序列中任选一个元素(假设为 pivot)作为中间元素,将所有比 pivot 小的元素移动到它的左边,所有比 pivot 大的元素移动到它的右边; pivot 左右两边的子序列看作是两个待排
本文向大家介绍浅析java 归并排序算法,包括了浅析java 归并排序算法的使用技巧和注意事项,需要的朋友参考一下 归并排序(Merge)是将两个(或两个以上)有序表合并成一个新的有序表,即把待排序序列分为若干个子序列,每个子序列是有序的。然后再把有序子序列合并为整体有序序列。 归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法(Divide and Conquer)的一个非常典型
本文向大家介绍java实现快速排序算法,包括了java实现快速排序算法的使用技巧和注意事项,需要的朋友参考一下 1、算法概念。 快速排序(Quicksort)是对冒泡排序的一种改进。由C. A. R. Hoare在1962年提出。 2、算法思想。 通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序
快速排序,这是一个经典的算法,本文给出几种python的写法,供参考。 特别是python能用一句话实现快速排序。 思路说明 快速排序是C.R.A.Hoare于1962年提出的一种划分交换排序。它采用了一种分治的策略,通常称其为分治法(Divide-and-ConquerMethod)。 (1) 分治法的基本思想 分治法的基本思想是:将原问题分解为若干个规模更小但结构与原问题相似的子问题。递归地解
本文向大家介绍PHP快速排序算法实例分析,包括了PHP快速排序算法实例分析的使用技巧和注意事项,需要的朋友参考一下 本文实例讲述了PHP快速排序算法。分享给大家供大家参考,具体如下: 快速排序:在无序的数组$data中,选择任意一个值作为对比值,定义i为头部检索索引,j为尾部检索索引, 算法步骤: (1)初始化对比值$value=$data[0],$i=1,$j=count($data)-1 (2
JavaScript算法-快速排序 快速排序是处理大数据集最快的排序算法之一。它是一种分而治之的算法,通过递归的方式将数据依次分解为包含较小元素和较大元素的不同子序列。该算法不断重复这个步骤直到所有数据都是有序的。 这个算法首先要在列表中选择一个元素作为基准值(pivot)。数据排序围绕基准值进行,将列表中小于基准值的元素移到数组的底部,将大于基准值的元素移到数组的顶部。 快速排序的算法和伪代码
快速排序(Quicksort)是对冒泡排序的一种改进,是一种排序执行效率很高的排序算法。 快速排序的基本思想是:通过一趟排序,将要排序的数据分隔成独立的两部分,其中一部分的所有数据比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此使整个数据变成有序序列。 具体做法是:假设要对某个数组进行排序,首先需要任意选取一个数据(通常选用第一个数据)作为