本文目录
- 排序算法有多少种
- 快速排序算法（free pascal)详解，不要源程序，时间复杂度n（logn）；谢了//
- 那位大大能详细的讲解一下JAVA中的快速排序
排序算法有多少种
排序(Sorting) 是计算机程序设计中的一种重要操作，它的功能是将一个数据元素（或记录）的任意序列，重新排列成一个关键字有序的序列。排序就是把集合中的元素按照一定的次序排序在一起。一般来说有升序排列和降序排列2种排序，在算法中有8中基本排序：(1)冒泡排序；(2)选择排序；(3)插入排序；(4)希尔排序；(5)归并排序；(6)快速排序；(7)基数排序；(8)堆排序；(9)计数排序；(10)桶排序。插入排序插入排序算法是基于某序列已经有序排列的情况下，通过一次插入一个元素的方式按照原有排序方式增加元素。这种比较是从该有序序列的最末端开始执行，即要插入序列中的元素最先和有序序列中最大的元素比较，若其大于该最大元素，则可直接插入最大元素的后面即可，否则再向前一位比较查找直至找到应该插入的位置为止。插入排序的基本思想是，每次将1个待排序的记录按其关键字大小插入到前面已经排好序的子序列中，寻找最适当的位置，直至全部记录插入完毕。执行过程中，若遇到和插入元素相等的位置，则将要插人的元素放在该相等元素的后面，因此插入该元素后并未改变原序列的前后顺序。我们认为插入排序也是一种稳定的排序方法。插入排序分直接插入排序、折半插入排序和希尔排序3类。冒泡排序冒泡排序算法是把较小的元素往前调或者把较大的元素往后调。这种方法主要是通过对相邻两个元素进行大小的比较，根据比较结果和算法规则对该二元素的位置进行交换，这样逐个依次进行比较和交换，就能达到排序目的。冒泡排序的基本思想是，首先将第1个和第2个记录的关键字比较大小，如果是逆序的，就将这两个记录进行交换，再对第2个和第3个记录的关键字进行比较，依次类推，重复进行上述计算，直至完成第(n一1)个和第n个记录的关键字之间的比较，此后，再按照上述过程进行第2次、第3次排序，直至整个序列有序为止。排序过程中要特别注意的是，当相邻两个元素大小一致时，这一步操作就不需要交换位置，因此也说明冒泡排序是一种严格的稳定排序算法，它不改变序列中相同元素之间的相对位置关系。选择排序选择排序算法的基本思路是为每一个位置选择当前最小的元素。选择排序的基本思想是，基于直接选择排序和堆排序这两种基本的简单排序方法。首先从第1个位置开始对全部元素进行选择，选出全部元素中最小的给该位置，再对第2个位置进行选择，在剩余元素中选择最小的给该位置即可；以此类推，重复进行“最小元素”的选择，直至完成第(n-1)个位置的元素选择，则第n个位置就只剩唯一的最大元素，此时不需再进行选择。使用这种排序时，要注意其中一个不同于冒泡法的细节。举例说明：序列58539．我们知道第一遍选择第1个元素“5”会和元素“3”交换，那么原序列中的两个相同元素“5”之间的前后相对顺序就发生了改变。因此，我们说选择排序不是稳定的排序算法，它在计算过程中会破坏稳定性。快速排序快速排序的基本思想是:通过一趟排序算法把所需要排序的序列的元素分割成两大块，其中，一部分的元素都要小于或等于另外一部分的序列元素，然后仍根据该种方法对划分后的这两块序列的元素分别再次实行快速排序算法，排序实现的整个过程可以是递归的来进行调用，最终能够实现将所需排序的无序序列元素变为一个有序的序列。归并排序归并排序算法就是把序列递归划分成为一个个短序列，以其中只有1个元素的直接序列或者只有2个元素的序列作为短序列的递归出口，再将全部有序的短序列按照一定的规则进行排序为长序列。归并排序融合了分治策略，即将含有n个记录的初始序列中的每个记录均视为长度为1的子序列，再将这n个子序列两两合并得到n/2个长度为2(当凡为奇数时会出现长度为l的情况)的有序子序列；将上述步骤重复操作，直至得到1个长度为n的有序长序列。需要注意的是，在进行元素比较和交换时，若两个元素大小相等则不必刻意交换位置，因此该算法不会破坏序列的稳定性，即归并排序也是稳定的排序算法。
快速排序算法（free pascal)详解，不要源程序，时间复杂度n（logn）；谢了//
快速排序是对冒泡排序的一种改进。它的基本思想是：通过一躺排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一不部分的所有数据都要小，然后再按次方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。 假设要排序的数组是A……A[N]，首先任意选取一个数据（通常选用第一个数据）作为关键数据，然后将所有比它的数都放到它前面，所有比它大的数都放到它后面，这个过程称为一躺快速排序。一躺快速排序的算法是： 1）、设置两个变量I、J，排序开始的时候I：=1，J：=N； 2）以第一个数组元素作为关键数据，赋值给X，即X：=A； 3）、从J开始向前搜索，即由后开始向前搜索（J：=J-1），找到第一个小于X的值，两者交换； 4）、从I开始向后搜索，即由前开始向后搜索（I：=I+1），找到第一个大于X的值，两者交换；5）、重复第3、4步，直到I》j；详细过程举例如下：原序： [26 5 37 1 61 11 59 15 48 19]一： [19 5 15 1 11] 26 [59 61 48 37]二： [11 5 15 1] 19 26 [59 61 48 37]三： [1 5] 11 19 26 [59 61 48 37]四： 1 5 11 19 26 [59 61 48 37]五： 1 5 11 15 19 26 [59 61 48 37]六： 1 5 11 15 19 26 [37 48] 59 七： 1 5 11 15 19 26 37 48 59 八： 1 5 11 15 19 26 37 48 59 61快速排序法是所有排序方法中速度最快、效率最高的方法。程序如下：var a:array[0..10] of integer； n:integer;procedure qsort(l,r:longint);{r，l表示集合的左右边界，即把第r到第l个数进行排序}var i,j,m:longint;begin m:=a[l];{标准数} i:=l; {I，J为指针} j:=r;repeat while a[i]《m do inc(i); while a[j]》m do dec(j); if i《=j then begin a:=a[i]; a[i]:=a[j]; a[j]:=a; inc(i); dec(j); end; until i》j;if l《j then qsort(l,j); {如果集合中不止一个数则进入下一层递归，l，J为新边界}if i《rthen qsort(i,r); {如果集合中不止一个数则进入下一层递归，i，r为新边界}end;begin for n:=1 to 10 do read(a[n]); qsort(1,10); for n:=1 to 10 do write(a[n]:4);end.
那位大大能详细的讲解一下JAVA中的快速排序
快速排序是对冒泡排序的一种改进。它的基本思想是：通过一躺排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按次方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。最坏情况的时间复杂度为O(n2)，最好情况时间复杂度为O(nlog2n)。另外 java没指针概念 可以认为是句柄假设要排序的数组是A……A[N]，首先任意选取一个数据（通常选用第一个数据）作为关键数据，然后将所有比它的数都放到它前面，所有比它大的数都放到它后面，这个过程称为一躺快速排序。一趟快速排序的算法是：1）、设置两个变量I、J，排序开始的时候I：=1，J：=N；2）以第一个数组元素作为关键数据，赋值给X，即X：=A；3）、从J开始向前搜索，即由后开始向前搜索（J：=J-1），找到第一个小于X的值，两者交换；4）、从I开始向后搜索，即由前开始向后搜索（I：=I+1），找到第一个大于X的值，两者交换；5）、重复第3、4步，直到I=J；例如：待排序的数组A的值分别是：（初始关键数据X：=49） A A A A A A A： 49 38 65 97 76 13 27进行第一次交换后： 27 38 65 97 76 13 49 ( 按照算法的第三步从后面开始找)进行第二次交换后： 27 38 49 97 76 13 65 ( 按照算法的第四步从前面开始找》X的值，65》49,两者交换，此时I：=3 )进行第三次交换后： 27 38 13 97 76 49 65( 按照算法的第五步将又一次执行算法的第三步从后开始找)进行第四次交换后： 27 38 13 49 76 97 65( 按照算法的第四步从前面开始找大于X的值，97》49,两者交换，此时J：=4 ) 此时再执行第三步的时候就发现I=J，从而结束一躺快速排序，那么经过一躺快速排序之后的结果是：27 38 13 49 76 97 65，即所以大于49的数全部在49的后面，所以小于49的数全部在49的前面。 快速排序就是递归调用此过程——在以49为中点分割这个数据序列，分别对前面一部分和后面一部分进行类似的快速排序，从而完成全部数据序列的快速排序，最后把此数据序列变成一个有序的序列，根据这种思想对于上述数组A的快速排序的全过程如图6所示：初始状态 {49 38 65 97 76 13 27} 进行一次快速排序之后划分为 {27 38 13} 49 {76 97 65}分别对前后两部分进行快速排序 {13} 27 {38} 结束 结束 {49 65} 76 {97} 49 {65} 结束 结束//下面是一个示例,哪位给说说快速排序法的原理,下面的示例中指针和上下标移动我看不太懂,public class QuickSort {/**主方法*/public static void main(String args) { //声明数组 int nums = {27, 8, 57, 9, 23, 41, 65, 19, 0, 1, 2, 4, 5}; //应用快速排序方法 quickSort(nums, 0, nums.length-1); //显示排序后的数组 for(int i = 0; i 《 nums.length; ++i) { System.out.print(nums[i] + “,“); } System.out.println(““);}/**快速排序方法*/public static void quickSort(int a, int lo0, int hi0) { int lo = lo0; int hi = hi0; if (lo 》= hi) return; //确定指针方向的逻辑变量 boolean transfer=true; while (lo != hi) { if (a[lo] 》 a[hi]) { //交换数字 int temp = a[lo]; a[lo] = a[hi]; a[hi] = temp; //决定下标移动，还是上标移动 transfer = (transfer == true) ? false : true; } //将指针向前或者向后移动 if(transfer) hi--; else lo++; //显示每一次指针移动的数组数字的变化 /*for(int i = 0; i 《 a.length; ++i) { System.out.print(a[i] + “,“); } System.out.print(“ (lo,hi) = “ + “(“ + lo + “,“ + hi + “)“); System.out.println(““);*/ } //将数组分开两半，确定每个数字的正确位置 lo--; hi++; quickSort(a, lo0, lo); quickSort(a, hi, hi0);}}