自助小站,长宁专业做网站,河北提供网站制作公司哪家好,成都网站排名生客seo怎么样排序问题一直是程序员工作与面试的重点#xff0c;今天特意整理研究下与大家共勉#xff01;这里列出8种常见的经典排序#xff0c;基本涵盖了所有的排序算法。 1.直接插入排序 我们经常会到这样一类排序问题#xff1a;把新的数据插入到已经排好的数据列中。将第一个数和第… 排序问题一直是程序员工作与面试的重点今天特意整理研究下与大家共勉这里列出8种常见的经典排序基本涵盖了所有的排序算法。 1.直接插入排序 我们经常会到这样一类排序问题把新的数据插入到已经排好的数据列中。将第一个数和第二个数排序然后构成一个有序序列将第三个数插入进去构成一个新的有序序列。对第四个数、第五个数……直到最后一个数重复第二步。如题所示 直接插入排序Straight Insertion Sorting的基本思想在要排序的一组数中假设前面(n-1) [n2] 个数已经是排好顺序的现在要把第n个数插到前面的有序数中使得这n个数也是排好顺序的。如此反复循环直到全部排好顺序。 代码实现 首先设定插入次数即循环次数for(int i1;ilength;i)1个数的那次不用插入。 设定插入数和得到已经排好序列的最后一个数的位数。insertNum和ji-1。 从最后一个数开始向前循环如果插入数小于当前数就将当前数向后移动一位。 将当前数放置到空着的位置即j1。 代码如下 1 public void insertSort(int [] a){2 int lena.length;//单独把数组长度拿出来提高效率3 int insertNum;//要插入的数4 for(int i1;ilen;i){//因为第一次不用所以从1开始5 insertNuma[i];6 int ji-1;//序列元素个数7 while(j0a[j]insertNum){//从后往前循环将大于insertNum的数向后移动8 a[j1]a[j];//元素向后移动9 j--;
10 }
11 a[j1]insertNum;//找到位置插入当前元素
12 }
13 } 2.希尔排序 针对直接插入排序的下效率问题有人对次进行了改进与升级这就是现在的希尔排序。希尔排序也称递减增量排序算法是插入排序的一种更高效的改进版本。希尔排序是非稳定排序算法。 希尔排序是基于插入排序的以下两点性质而提出改进方法的 插入排序在对几乎已经排好序的数据操作时 效率高 即可以达到线性排序的效率但插入排序一般来说是低效的 因为插入排序每次只能将数据移动一位如图所示 对于直接插入排序问题数据量巨大时。 将数的个数设为n取奇数kn/2将下标差值为k的数分为一组构成有序序列。 再取kk/2 将下标差值为k的书分为一组构成有序序列。 重复第二步直到k1执行简单插入排序。 代码实现 首先确定分的组数。 然后对组中元素进行插入排序。 然后将length/2重复1,2步直到length0为止。 1 public void sheelSort(int [] a){2 int lena.length;//单独把数组长度拿出来提高效率3 while(len!0){4 lenlen/2;5 for(int i0;ilen;i){//分组6 for(int jilen;ja.length;jlen){//元素从第二个开始7 int kj-len;//k为有序序列最后一位的位数8 int tempa[j];//要插入的元素9 /*for(;k0tempa[k];k-len){
10 a[klen]a[k];
11 }*/
12 while(k0tempa[k]){//从后往前遍历
13 a[klen]a[k];
14 k-len;//向后移动len位
15 }
16 a[klen]temp;
17 }
18 }
19 }
20 } 3.简单选择排序 常用于取序列中最大最小的几个数时。 (如果每次比较都交换那么就是交换排序如果每次比较完一个循环再交换就是简单选择排序。) 遍历整个序列将最小的数放在最前面。 遍历剩下的序列将最小的数放在最前面。 重复第二步直到只剩下一个数。 代码实现 首先确定循环次数并且记住当前数字和当前位置。 将当前位置后面所有的数与当前数字进行对比小数赋值给key并记住小数的位置。 比对完成后将最小的值与第一个数的值交换。 重复2、3步。 1 public void selectSort(int[]a){2 int lena.length;3 for(int i0;ilen;i){//循环次数4 int valuea[i];5 int positioni;6 for(int ji1;jlen;j){//找到最小的值和位置7 if(a[j]value){8 valuea[j];9 positionj;
10 }
11 }
12 a[position]a[i];//进行交换
13 a[i]value;
14 }
15 } 4.堆排序 对简单选择排序的优化。 将序列构建成大顶堆。 将根节点与最后一个节点交换然后断开最后一个节点。 重复第一、二步直到所有节点断开。 代码如下 1 public void heapSort(int[] a){2 int lena.length;3 //循环建堆 4 for(int i0;ilen-1;i){5 //建堆 6 buildMaxHeap(a,len-1-i);7 //交换堆顶和最后一个元素 8 swap(a,0,len-1-i);9 }
10 }
11 //交换方法
12 private void swap(int[] data, int i, int j) {
13 int tmpdata[i];
14 data[i]data[j];
15 data[j]tmp;
16 }
17 //对data数组从0到lastIndex建大顶堆
18 private void buildMaxHeap(int[] data, int lastIndex) {
19 //从lastIndex处节点最后一个节点的父节点开始
20 for(int i(lastIndex-1)/2;i0;i--){
21 //k保存正在判断的节点
22 int ki;
23 //如果当前k节点的子节点存在
24 while(k*21lastIndex){
25 //k节点的左子节点的索引
26 int biggerIndex2*k1;
27 //如果biggerIndex小于lastIndex即biggerIndex1代表的k节点的右子节点存在
28 if(biggerIndexlastIndex){
29 //若果右子节点的值较大
30 if(data[biggerIndex]data[biggerIndex1]){
31 //biggerIndex总是记录较大子节点的索引
32 biggerIndex;
33 }
34 }
35 //如果k节点的值小于其较大的子节点的值
36 if(data[k]data[biggerIndex]){
37 //交换他们
38 swap(data,k,biggerIndex);
39 //将biggerIndex赋予k开始while循环的下一次循环重新保证k节点的值大于其左右子节点的值
40 kbiggerIndex;
41 }else{
42 break;
43 }
44 }
45 }
46 } 5.冒泡排序 很简单用到的很少据了解面试的时候问的比较多 将序列中所有元素两两比较将最大的放在最后面。 将剩余序列中所有元素两两比较将最大的放在最后面。 重复第二步直到只剩下一个数。 代码实现 设置循环次数。 设置开始比较的位数和结束的位数。 两两比较将最小的放到前面去。 重复2、3步直到循环次数完毕。 1 public void bubbleSort(int []a){2 int lena.length;3 for(int i0;ilen;i){4 for(int j0;jlen-i-1;j){//注意第二重循环的条件5 if(a[j]a[j1]){6 int tempa[j];7 a[j]a[j1];8 a[j1]temp;9 }
10 }
11 }
12 } 6.快速排序 要求时间最快时。 选择第一个数为p小于p的数放在左边大于p的数放在右边。 递归的将p左边和右边的数都按照第一步进行直到不能递归。 1 public void quickSort(int[]a,int start,int end){2 if(startend){3 int baseNuma[start];//选基准值4 int midNum;//记录中间值5 int istart;6 int jend;7 do{8 while((a[i]baseNum)iend){9 i;
10 }
11 while((a[j]baseNum)jstart){
12 j--;
13 }
14 if(ij){
15 midNuma[i];
16 a[i]a[j];
17 a[j]midNum;
18 i;
19 j--;
20 }
21 }while(ij);
22 if(startj){
23 quickSort(a,start,j);
24 }
25 if(endi){
26 quickSort(a,i,end);
27 }
28 }
29 } 7.归并排序 速度仅次于快速排序内存少的时候使用可以进行并行计算的时候使用。 选择相邻两个数组成一个有序序列。 选择相邻的两个有序序列组成一个有序序列。 重复第二步直到全部组成一个有序序列。 1 public void mergeSort(int[] a, int left, int right) { 2 int t 1;// 每组元素个数 3 int size right - left 1; 4 while (t size) { 5 int s t;// 本次循环每组元素个数 6 t 2 * s; 7 int i left; 8 while (i (t - 1) size) { 9 merge(a, i, i (s - 1), i (t - 1));
10 i t;
11 }
12 if (i (s - 1) right)
13 merge(a, i, i (s - 1), right);
14 }
15 }
16
17 private static void merge(int[] data, int p, int q, int r) {
18 int[] B new int[data.length];
19 int s p;
20 int t q 1;
21 int k p;
22 while (s q t r) {
23 if (data[s] data[t]) {
24 B[k] data[s];
25 s;
26 } else {
27 B[k] data[t];
28 t;
29 }
30 k;
31 }
32 if (s q 1)
33 B[k] data[t];
34 else
35 B[k] data[s];
36 for (int i p; i r; i)
37 data[i] B[i];
38 } 8.基数排序 用于大量数很长的数进行排序时。 将所有的数的个位数取出按照个位数进行排序构成一个序列。 将新构成的所有的数的十位数取出按照十位数进行排序构成一个序列。 代码实现 1 public void baseSort(int[] a) {2 //首先确定排序的趟数; 3 int max a[0];4 for (int i 1; i a.length; i) {5 if (a[i] max) {6 max a[i];7 }8 }9 int time 0;
10 //判断位数;
11 while (max 0) {
12 max / 10;
13 time;
14 }
15 //建立10个队列;
16 ListArrayListInteger queue new ArrayListArrayListInteger();
17 for (int i 0; i 10; i) {
18 ArrayListInteger queue1 new ArrayListInteger();
19 queue.add(queue1);
20 }
21 //进行time次分配和收集;
22 for (int i 0; i time; i) {
23 //分配数组元素;
24 for (int j 0; j a.length; j) {
25 //得到数字的第time1位数;
26 int x a[j] % (int) Math.pow(10, i 1) / (int) Math.pow(10, i);
27 ArrayListInteger queue2 queue.get(x);
28 queue2.add(a[j]);
29 queue.set(x, queue2);
30 }
31 int count 0;//元素计数器;
32 //收集队列元素;
33 for (int k 0; k 10; k) {
34 while (queue.get(k).size() 0) {
35 ArrayListInteger queue3 queue.get(k);
36 a[count] queue3.get(0);
37 queue3.remove(0);
38 count;
39 }
40 }
41 }
42 } 新建测试类进行测试 1 public class TestSort {2 public static void main(String[] args) {3 int []anew int[10];4 for(int i1;ia.length;i){5 //a[i](int)(new Random().nextInt(100));6 a[i](int)(Math.random()*100);7 }8 System.out.println(排序前的数组为Arrays.toString(a));9 Sort snew Sort();
10 //排序方法测试
11 //s.insertSort(a);
12 //s.sheelSort(a);
13 //s.selectSort(a);
14 //s.heapSort(a);
15 //s.bubbleSort(a);
16 //s.quickSort(a, 1, 9);
17 //s.mergeSort(a, 3, 7);
18 s.baseSort(a);
19 System.out.println(排序后的数组为Arrays.toString(a));
20 }
21
22 } 部分结果如下: 如果要进行比较可已加入时间输出排序时间从而比较各个排序算法的优缺点这里不再做介绍。 8.总结 一、稳定性: 稳定冒泡排序、插入排序、归并排序和基数排序 不稳定选择排序、快速排序、希尔排序、堆排序 二、平均时间复杂度 O(n^2):直接插入排序简单选择排序冒泡排序。 在数据规模较小时9W内直接插入排序简单选择排序差不多。当数据较大时冒泡排序算法的时间代价最高。性能为O(n^2)的算法基本上是相邻元素进行比较基本上都是稳定的。 O(nlogn):快速排序归并排序希尔排序堆排序。 其中快排是最好的 其次是归并和希尔堆排序在数据量很大时效果明显。 三、排序算法的选择 1.数据规模较小 1待排序列基本序的情况下可以选择直接插入排序 2对稳定性不作要求宜用简单选择排序对稳定性有要求宜用插入或冒泡 2.数据规模不是很大 1完全可以用内存空间序列杂乱无序对稳定性没有要求快速排序此时要付出logN的额外空间。 2序列本身可能有序对稳定性有要求空间允许下宜用归并排序 3.数据规模很大 1对稳定性有求则可考虑归并排序。 2对稳定性没要求宜用堆排序 4.序列初始基本有序正序宜用直接插入冒泡 各算法复杂度如下 部分参考资料来源于 http://blog.csdn.net/without0815/article/details/7697916
