基本排序的实现及比较分析
重拾算法,从基本写起。我觉得在算法中除了作为基础的数据结构,基本中的基本就是排序。
闲话不多说,我想分析的排序包括以下几种:鸡尾酒排序(双向冒泡)、快速排序、归并排序、堆排序、基数排序。
1.鸡尾酒排序
嘿嘿,这个排序名字很好听,其实是在这几种排序中最简单的,当然效率显然也是低下的。思想是这样的,首先是0—n,选出最小的放在第0号位置,最大的放在n号位置,接着对1—(n-1)执行同样地操作。当i>j了终止(i是起始位置,j是终止位置)。平均时间复杂度为O(n2),虽然这个时间复杂度和冒泡一样,但显而易见,与冒泡相比,访问原序列的次数大大减少了。以下是Java版代码
当然这里可以在比较中记录最大和最小的索引,实现在循环一次交换但其实是一个性质,这里不加以优化。
2.快速排序
学计算机的同学肯定都懂的。快排作为学数据结构必须掌握的算法之一,有着良好的性能。在这里我列出的几种排序中,快排是排序中平均速度最快的,但简单的快排是不稳定的,所以在特殊情况下可能和冒泡近似。来说说快排的原理:
选用了百度中的一张截图作为指针移动示例,快排中最重要的就是两个指针(在Java中可以说是两个索引)的移动和与Key值得交换,指针分别为头指针和尾指针,Key值为比较值,一趟快排的目的是确定Key所在的位置,并且使Key之前的数均小于Key,之后的数均大于Key。初始化时,Key值一般设为第一个数(这时头指针指向Key值),尾指针指向末尾(示例中Key为49,头指针指向49,尾指针指向27)。这时从尾指针开始向前,一个个比较,当指向值小于Key值时,将Key值与该值交换,然后头指针开始向后移动,当该值大于Key值是交换,然后尾指针继续移动,这样循环直到头尾指针指向同一个位置,此时一趟排序结束,接下去就很简单,调用递归,对Key的前半部分和后半部分分别进行快排。示例中,一趟快排的结果为:
27 38 13 49 76 97 65
在写代码时,要注意的是,Key的位置最后肯定在头尾指针重合处,所以在之前交换的时候,只需将需要交换的值赋给Key值所在的位置,而不用实质意义上的交换。个人觉得快排很好很强大。
可以看到在写快排的时候我用到了随机数,这是为了防止当出现倒序的时候使快排褪变为冒泡而采取的优化,即随机取一个范围内的索引与起始位置交换并作为Key值。当然这种快排在出现许多重复值时仍会出现极端情况,快排的平均时间复杂度为nlogn。
3.堆排序
说到堆排序,首先先说说最小、大堆。以最大堆为例,最大堆是一种二叉堆,从实现上来说的说就是一棵完全二叉树,其中任意一个子堆或者说子树中根节点均大于两个子节点,所以整棵树的根节点为这棵树的最大值。而完全二叉树的存储方式就可以用数组来实现了。用数组模拟完全二叉树,假如在数组中的索引为n,那么这个结点在二叉树中的子节点在数组中的索引分别为(2n+1)和(2n+2)(很巧妙啊)。那怎么样来建堆呢?这就是仁者见仁智者见智了,比如插入法等。我这里采用的是一种比较简单的方法,从小到大,自上而下,是每个子堆都为一个最大堆,并且需要调整时,从子堆根结点开始向下调整。以途中二叉树为例讲解:
首先需要找到最后一个拥有子节点的根节点,即n/2(数组中索引是(n-1)/2),这个根节点所在的堆是最小并且最靠后的子堆,然后从这个结点向左走(走到最左边就跳到上一层最右边继续),每走到一个点就把那个结点作为根的树变为最大堆,具体操作就是如果根比左右子节点中较大的那个节点小,则与之交换,并且继续向下走直到走到叶节点位置。图中,先12与6交换,然后当走到3时,3的两个子节点分别为12和7,与12交换,然后再与6交换(6为叶节点)。学会了建最大堆,那就简单了,对一个长度为n的数组排序,首先对0—(n-1)调整,然后把0与(n-1)交换,然后对0—(n-2)调整,再交换,每次都把最大的数往后抛,堆排序就完成了!!!(不知道看懂了没。。。)
代码中又可以优化的地方,比如在第一次建堆后调整时,只需要直接从根结点向下走一遍即可。
堆排序的时间复杂度为nlogn,而且是一种相对稳定的排序算法,这在后面的比较中可以明显看到。
4.归并排序
比较容易理解的一种排序,这里特指二路归并,就是把数组分成两份(等分),把两份头排好序后就合并,按照思路比较好的方法就是递归的思想(当然非递归也是可以的)。主要的优化是在合并的时候。分别用两个数记录两段数组的起始位置,然后比较,小的那个数插入到一个临时数组中,然后小的数的索引向后走,直到把其中一段数组走完,剩下就是把没走完的那一段数组直接放在临时数组的最后一段,这样就排好序了。显而易见的缺点就是需要一个多余的数组空间。时间复杂度上来讲是nlogn,也是一种稳定的排序,并且按理论上来说在大数组时应该快于堆排序(测试中好像不是这样。。。)
为了减少空间的浪费,我就定义了一个temp数组,让排序在temp中进行部分调整。
5.基数排序
说白了就是根据键值的大小进行排序。比如n个整数,最大的为三位数,那么百位大的数肯定最大,十位大的其次,个位相对最不重要。所以简单的基数排序分为这么几步(采用最低键值LDS):一、计算数组中的最高位(整数的话就是长度) 二、建立一个长度为10的链表数组,从键值最轻的开始(个位),根据个位数的值,分别放入相应数组中的链表中 三、收集。对数组中的数,从数组的索引0-9进行收集,成为一个新的序列,这是一趟基数排序完成。四、重复二、三步骤,其中键值依次增重,(即个位,然后十位,百位.....)。时间复杂度为O (nlog(r)m),当然也是一种稳定的排序。
呵呵,看了这个代码,高手肯定想吐血,不过,对于这个排序我只是想说明他在重复值较多的时候的高效性,所以即使采用了库中的类(链表队列),性能还是很好区分的。
6.测试
写完了这几种排序后,对这种排序进行了一个测试,不包括鸡尾酒排序(双向冒泡还是太慢了),测试类如下
第一次采用随机数,数据量为1000000,数据在0-10000,结果如下:
系统排序指的是Arrays.sort(),比较下可以发现相对而言堆排序时间比较快。
第二次采用倒序的序列,数据量为1000000,结果如下:
闲话不多说,我想分析的排序包括以下几种:鸡尾酒排序(双向冒泡)、快速排序、归并排序、堆排序、基数排序。
1.鸡尾酒排序
嘿嘿,这个排序名字很好听,其实是在这几种排序中最简单的,当然效率显然也是低下的。思想是这样的,首先是0—n,选出最小的放在第0号位置,最大的放在n号位置,接着对1—(n-1)执行同样地操作。当i>j了终止(i是起始位置,j是终止位置)。平均时间复杂度为O(n2),虽然这个时间复杂度和冒泡一样,但显而易见,与冒泡相比,访问原序列的次数大大减少了。以下是Java版代码
public class CocktailSort { public void cocktailSort(int[] data) { int sta = 0; int i; int end = data.length - 1; while (sta < end) { for (i = sta; i < end; i++) { if (data[i] > data[i + 1]) { int t = data[i]; data[i] = data[i + 1]; data[i + 1] = t; } } end--; for (i = end; i > sta; i--) { if (data[i] < data[i - 1]) { int t = data[i]; data[i] = data[i - 1]; data[i - 1] = t; } } sta++; } } }
当然这里可以在比较中记录最大和最小的索引,实现在循环一次交换但其实是一个性质,这里不加以优化。
2.快速排序
学计算机的同学肯定都懂的。快排作为学数据结构必须掌握的算法之一,有着良好的性能。在这里我列出的几种排序中,快排是排序中平均速度最快的,但简单的快排是不稳定的,所以在特殊情况下可能和冒泡近似。来说说快排的原理:
选用了百度中的一张截图作为指针移动示例,快排中最重要的就是两个指针(在Java中可以说是两个索引)的移动和与Key值得交换,指针分别为头指针和尾指针,Key值为比较值,一趟快排的目的是确定Key所在的位置,并且使Key之前的数均小于Key,之后的数均大于Key。初始化时,Key值一般设为第一个数(这时头指针指向Key值),尾指针指向末尾(示例中Key为49,头指针指向49,尾指针指向27)。这时从尾指针开始向前,一个个比较,当指向值小于Key值时,将Key值与该值交换,然后头指针开始向后移动,当该值大于Key值是交换,然后尾指针继续移动,这样循环直到头尾指针指向同一个位置,此时一趟排序结束,接下去就很简单,调用递归,对Key的前半部分和后半部分分别进行快排。示例中,一趟快排的结果为:
27 38 13 49 76 97 65
在写代码时,要注意的是,Key的位置最后肯定在头尾指针重合处,所以在之前交换的时候,只需将需要交换的值赋给Key值所在的位置,而不用实质意义上的交换。个人觉得快排很好很强大。
import java.util.Random; public class Qsort { /** * 快速排序 * @param i:起始位置(包含) * @param j:末位置(包含) * @param data:需要排序的数组 */ public void qSort(int i, int j, int[] data) { int st = i;//头指针 int ed = j;//尾指针 if (i < j) { int id=(int)(Math.random()*(j-i))+i; int key=data[id]; data[id]=data[st]; data[st]=key; while (st < ed) { while (data[ed] >= key && st < ed) ed--; data[st] = data[ed]; while (data[st] <= key && st < ed) st++; data[ed] = data[st]; } data[ed] = key; qSort(i, ed - 1, data); qSort(ed + 1, j, data); } } }
可以看到在写快排的时候我用到了随机数,这是为了防止当出现倒序的时候使快排褪变为冒泡而采取的优化,即随机取一个范围内的索引与起始位置交换并作为Key值。当然这种快排在出现许多重复值时仍会出现极端情况,快排的平均时间复杂度为nlogn。
3.堆排序
说到堆排序,首先先说说最小、大堆。以最大堆为例,最大堆是一种二叉堆,从实现上来说的说就是一棵完全二叉树,其中任意一个子堆或者说子树中根节点均大于两个子节点,所以整棵树的根节点为这棵树的最大值。而完全二叉树的存储方式就可以用数组来实现了。用数组模拟完全二叉树,假如在数组中的索引为n,那么这个结点在二叉树中的子节点在数组中的索引分别为(2n+1)和(2n+2)(很巧妙啊)。那怎么样来建堆呢?这就是仁者见仁智者见智了,比如插入法等。我这里采用的是一种比较简单的方法,从小到大,自上而下,是每个子堆都为一个最大堆,并且需要调整时,从子堆根结点开始向下调整。以途中二叉树为例讲解:
首先需要找到最后一个拥有子节点的根节点,即n/2(数组中索引是(n-1)/2),这个根节点所在的堆是最小并且最靠后的子堆,然后从这个结点向左走(走到最左边就跳到上一层最右边继续),每走到一个点就把那个结点作为根的树变为最大堆,具体操作就是如果根比左右子节点中较大的那个节点小,则与之交换,并且继续向下走直到走到叶节点位置。图中,先12与6交换,然后当走到3时,3的两个子节点分别为12和7,与12交换,然后再与6交换(6为叶节点)。学会了建最大堆,那就简单了,对一个长度为n的数组排序,首先对0—(n-1)调整,然后把0与(n-1)交换,然后对0—(n-2)调整,再交换,每次都把最大的数往后抛,堆排序就完成了!!!(不知道看懂了没。。。)
public class HeapSort { /** * 调整子堆 * @param i:起始位置 * @param j:终止位置 * @param data:需要排序的数组 */ public void AdjustHeap(int s,int e,int[] data) { for(int i=s*2+1;i<e;i=i*2+1) { if(data[i]<data[i+1]) { i=i+1; } if(data[s]>=data[i]) break; else { int t=data[i]; data[i]=data[s]; data[s]=t; } s=i; } } public void heapSort(int[] data) { int n=data.length-1; for(int i=(n-1)/2;i>=0;i--)//第一次建堆 { AdjustHeap(i,n, data); } for(int i=data.length-1;i>=0;i--) { int t=data[0]; data[0]=data[i]; data[i]=t; AdjustHeap(0, i-1, data); } } }
代码中又可以优化的地方,比如在第一次建堆后调整时,只需要直接从根结点向下走一遍即可。
堆排序的时间复杂度为nlogn,而且是一种相对稳定的排序算法,这在后面的比较中可以明显看到。
4.归并排序
比较容易理解的一种排序,这里特指二路归并,就是把数组分成两份(等分),把两份头排好序后就合并,按照思路比较好的方法就是递归的思想(当然非递归也是可以的)。主要的优化是在合并的时候。分别用两个数记录两段数组的起始位置,然后比较,小的那个数插入到一个临时数组中,然后小的数的索引向后走,直到把其中一段数组走完,剩下就是把没走完的那一段数组直接放在临时数组的最后一段,这样就排好序了。显而易见的缺点就是需要一个多余的数组空间。时间复杂度上来讲是nlogn,也是一种稳定的排序,并且按理论上来说在大数组时应该快于堆排序(测试中好像不是这样。。。)
public class MergeSort { int[] temp; /** * * @param len:数组长度 */ public MergeSort(int len) { // TODO Auto-generated constructor stub temp=new int[len]; } /** * 进行归并 * * @param data * :数组 * @param st * :前半部分 * @param mid * :分界 * @param end * :后半部分 */ public void merSort(int[] data, int st, int mid, int end) { int k = st; int i = st; int j = mid + 1; for (; i < mid + 1 && j <= end; k++) { if (data[i] <= data[j]) { temp[k] = data[i]; i++; } else { temp[k] = data[j]; j++; } } for (; i < mid + 1; i++,k++) temp[k] = data[i]; for (; j < end + 1; j++,k++) temp[k] = data[j]; for (i =st; i < end+1; i++) data[i] = temp[i]; } /** * 对数组的st到end进行排序 * * @param data * :需要排序的数组 * @param st * :排序的起始位置 * @param end * :排序的末位置 */ public void sortHelp(int[] data, int st, int end) { int mid = (st + end) / 2; if (st<end) { sortHelp(data, st, mid); sortHelp(data, mid + 1, end); merSort(data, st, mid, end); } else return; } }
为了减少空间的浪费,我就定义了一个temp数组,让排序在temp中进行部分调整。
5.基数排序
说白了就是根据键值的大小进行排序。比如n个整数,最大的为三位数,那么百位大的数肯定最大,十位大的其次,个位相对最不重要。所以简单的基数排序分为这么几步(采用最低键值LDS):一、计算数组中的最高位(整数的话就是长度) 二、建立一个长度为10的链表数组,从键值最轻的开始(个位),根据个位数的值,分别放入相应数组中的链表中 三、收集。对数组中的数,从数组的索引0-9进行收集,成为一个新的序列,这是一趟基数排序完成。四、重复二、三步骤,其中键值依次增重,(即个位,然后十位,百位.....)。时间复杂度为O (nlog(r)m),当然也是一种稳定的排序。
import java.util.ArrayDeque; public class RadixSort { /** * 基数排序 * * @param data * :对象数组 * @param len * :数据最高位数 */ public void radixSort(int[] data, int len) { int size = data.length; int radix = 1; ArrayDeque<Integer>[] li = new ArrayDeque[10]; for (int i = 1; i <= len; i++) { // 分配 for (int j = 0; j < size; j++) { int index = (data[j] / radix) % 10; if (li[index] == (null)) li[index] = new ArrayDeque<Integer>(); li[index].add(data[j]); } int k = 0; for (int j = 0; j < 10; j++) { ArrayDeque<Integer> ab = li[j]; if (ab != null) { while(!ab.isEmpty()){ data[k] = ab.pollFirst(); k++;} ab.clear(); } } radix = radix * 10; } } }
呵呵,看了这个代码,高手肯定想吐血,不过,对于这个排序我只是想说明他在重复值较多的时候的高效性,所以即使采用了库中的类(链表队列),性能还是很好区分的。
6.测试
写完了这几种排序后,对这种排序进行了一个测试,不包括鸡尾酒排序(双向冒泡还是太慢了),测试类如下
import java.util.Arrays; import java.util.Date; import java.util.Random; public class Test { public static void main(String[] args) { Random ran = new Random(); int num = 1000000; int[] data = new int[1000000]; int[] data1 = new int[1000000]; int[] data2 = new int[1000000]; int[] data3 = new int[1000000]; int[] data4 = new int[1000000]; int[] data5 = new int[1000000]; int biglen=0; for (int i = 0; i < num; i++) { data[i] =ran.nextInt(10000)+1; if(biglen<String.valueOf(data[i]).length()); biglen=String.valueOf(data[i]).length(); data1[i] = data[i]; data2[i] = data[i]; data3[i] = data[i]; data4[i] = data[i]; data5[i] = data[i]; } System.out.println("输入完毕"+biglen); data1 = data; int len=data3.length; Qsort qsort = new Qsort(); HeapSort hsort = new HeapSort(); MergeSort msort=new MergeSort(len); //CocktailSort csort=new CocktailSort(); RadixSort rsort=new RadixSort(); Date da = new Date(); long a = da.getTime(); qsort.qSort(0, data1.length - 1, data1); da = new Date(); long b = da.getTime(); System.out.println("快速排序 time=" + (b - a)); da = new Date(); a = da.getTime(); hsort.heapSort(data); da = new Date(); b = da.getTime(); System.out.println("堆排序 time=" + (b - a)); da = new Date(); a = da.getTime(); Arrays.sort(data2); da = new Date(); b = da.getTime(); System.out.println("系统排序 time=" + (b - a)); da = new Date(); a = da.getTime(); msort.sortHelp(data3, 0, len-1); da = new Date(); b = da.getTime(); System.out.println("归并排序 time=" + (b - a)); da = new Date(); a = da.getTime(); rsort.radixSort(data5, biglen); da = new Date(); b = da.getTime(); System.out.println("基数排序 time=" + (b - a)); } }
第一次采用随机数,数据量为1000000,数据在0-10000,结果如下:
系统排序指的是Arrays.sort(),比较下可以发现相对而言堆排序时间比较快。
第二次采用倒序的序列,数据量为1000000,结果如下:
相关推荐
3. 掌握各种排序方法的优劣分析及花费的时间的计算。 4. 掌握各种排序方法所适应的不同场合。 此设计题目要求了解掌握各种排序算法、分析其优劣。故设计总体框架如下:定义一个主函数,在主函数中定义一个长度...
实现以下常用的内部排序算法并进行性能比较:"直接插入排序"," 折半插入排序"," 2—路插入排序"," 表插入排序"," 希尔排序"," 起泡排序"," 快速排序"," 简单选择排序"," 树形选择排序"," 堆排序"," 归并排序"," 链式...
java 实现归并排序,有代码实现,复杂度分析,基本步骤,适合初学者吧,
排序(Sorting) 是计算机程序设计中的一种重要操作,它的功能是将一个数据元素(或记录)的...本文主要介绍快速排序算法和归并排序算法的基本概念、原理以及具体的实现方法,并对这两种排序算法的时间复杂度进行分析。
第三部分“排序”(第6~11章)按章节顺序分别讨论基本排序方法(如选择排序、插入排序、冒泡排序、希尔排序等)、快速排序方法、归并和归并排序方法、优先队列与堆排序方法、基数排序方法以及特殊用途的排序方法,...
包括基本算法分析原理,基本数据结构、抽象数据结构、递归和树等数据结构知识,选择排序、插入排序、冒泡排序、希尔排序、快速排序方法、归并和归并排序方法、优先队列与堆排序方法、基数排序方法以及特殊用途的排序...
(2)需要实现起泡排序(Bubble)、直接插入排序(Insert)、简单选择排序(Select)、快速排序(Quick)、希尔排序(Shell)、堆排序(Heap)几种基本排序算法。 (3)需要实现数据的插入操作,将五组数据存入...
(1)实现各种内部排序。包括冒泡排序,直接选择排序,希尔排序,快速排序,堆排序。 (2) 待排序的元素的关键字为整数。其中的数据要用随机数产生(如10000个),至少用5组不同的数据做比较,再使用各种算法对其进行排序...
对以下常用的内部排序算法进行比较:起泡排序、直接插入排序、简单选择排序、快速排序、希尔排序、堆排序。 [测试数据] 由随机产生器决定。 [实现提示] 待排序表的表长不少于100;其中的数据要用伪随机数产生...
内部排序算法的时间分析 课程设计 基本上实现了八种内部排序算法的时间性能分析
算法分析课程设计图的基本操作与实现 成绩分析文档资料 【问题描述】:录入、保存一个班级学生多门课程的成绩,并对成绩进行分析。 【需求分析】: 1.通过键盘输入各学生的多门课程的成绩,建立相应的文件"student...
内部排序算法比较 【问题描述】 在教科书中,各种内部排序算法的时间复杂度分析结果只给出了算法执行时间的阶,或大概执行时间。试通过随机数据比较各算法的关键字比较次数和关键字移动次数,以取得直观感受。 ...
《福建电脑报》上的一篇文章,作者为滨州学院的刘春霞、常璐璐,以前读过,上传以便继续研究,在此对作者表示感谢。... 本文列举出几种常用排序的基本思想、算法实现及算法分析.并给出这些排序算法的比较和选择。
排序问题要求我们按照...通过对大量样本的测试结果,统计不同排序算法的时间效率与输入规模的关系,通过经验分析方法,展示不同排序算法的时间复杂度,并与理论分析的基本运算次数做比较,验证理论分析结论的正确性。
实验题目:排序方法的实现与实验比较 实验内容: 实现一组经典的排序算法,通过实验数据的设计,考察不同规模和分布(正 序序列、反序序列和随机序列)的数据对排序算法运行时间影响的规律,验证理 论分析结果的...
通过实验,帮助学生由浅入深地掌握各种简单排序和高级排序的基本思想,让他们比较其性能,也让他们更好地理解希尔排序和快速排序的方法。 1.任意输入一个数组并利用简单选择排序算法对此数组的元素按从大到小的顺序...
兰州理工大学 二分查找算法、起泡排序、简单选择排序、直接插入排序、二分插入排序、快速排序算法
⑴至少采用三种方法实现上述问题求解(提示,可采用的方法有插入排序、希尔排序、起泡排序、快速排序、选择排序、堆排序、归并排序)。 ⑵待排序表的表长不小于100,其中的数据要用伪随机数产生程序产生;至少要用5...
1、编程实现冒泡排序算法 2、编程实现快速排序算法 3、编程实现插入排序算法 4、采用上述算法对序列进行排序并统计时间开销 5、对比算法时间效率并分析其原因
讲解了选择排序的基本原理,并用C++实现了简单选择排序,和堆排序算法,并进行了算法复杂度的分析。