Java程序员必知的8大排序及详解
Java程序员必知的8大排序
2012-06-28 14:01 without0815 博客园我要评论(5)字号：T | T
本文主要详解了Java语言的8大排序的基本思想以及实例解读，详细请看下文
AD：51CTO云计算架构师峰会抢票进行中！
8种排序之间的关系:
1，直接插入排序
（1）基本思想：在要排序的一组数中，假设前面(n-1)[n>=2] 个数已经是排
好顺序的，现在要把第n个数插到前面的有序数中，使得这n个数
也是排好顺序的。如此反复循环，直到全部排好顺序。
（2）实例
（3）用java实现
1package com.njue;
2
3public class insertSort {
4public insertSort(){
5inta[]={49,38,65,97,76,13,27,49,78,34,12,64,5,4,62,99,98,54,56,17,18,2 3,34,15,35,25,53,51};
6int temp=0;
7for(int i=1;i 8int j=i-1; 9temp=a[i]; 10for(;j>=0&&temp 11a[j+1]=a[j]; //将大于temp的值整体后移一个单位 12} 13a[j+1]=temp; 14} 15for(int i=0;i 16System.out.println(a[i]); 17} 18} 2，希尔排序（最小增量排序） （1）基本思想：算法先将要排序的一组数按某个增量d（n/2,n为要排序数的个数）分成若干组，每组中记录的下标相差d.对每组中全部元素进行直接插入排序，然后再用一个较小的增量（d/2）对它进行分组，在每组中再进行直接插入排序。当增量减到1时，进行直接插入排序后，排序完成。 （2）实例： （3）用java实现 19public class shellSort { 20public shellSort(){ 21int a[]={1,54,6,3,78,34,12,45,56,100}; 22double d1=a.length; 23int temp=0; 24while(true){ 25d1= Math.ceil(d1/2); 26int d=(int) d1; 27for(int x=0;x 28for(int i=x+d;i 29int j=i-d; 30temp=a[i]; 31for(;j>=0&&temp 32a[j+d]=a[j]; 33} 34a[j+d]=temp; 35} 36} 37if(d==1) 38break; 39} 40for(int i=0;i 41System.out.println(a[i]); 42} 43} 3.简单选择排序 （1）基本思想：在要排序的一组数中，选出最小的一个数与第一个位置的数交换； 然后在剩下的数当中再找最小的与第二个位置的数交换，如此循环到倒数第二个数和最后一个数比较为止。 （2）实例： （3）用java实现 44public class selectSort { 45public selectSort(){ 46int a[]={1,54,6,3,78,34,12,45}; 47int position=0; 48for(int i=0;i 49 50int j=i+1; 51position=i; 52int temp=a[i]; 53for(;j 54if(a[j] 55temp=a[j]; 56position=j; 57} 58} 59a[position]=a[i]; 60a[i]=temp; 61} 62for(int i=0;i 63System.out.println(a[i]); 64} 65} 4，堆排序 （1）基本思想：堆排序是一种树形选择排序，是对直接选择排序的有效改进。 堆的定义如下：具有n个元素的序列（h1,h2,...,hn),当且仅当满足（hi>=h2i,hi>=2i+1）或（hi<=h2i,hi<=2i+1）(i=1,2,...,n/2)时称之为堆。在这里只讨论满足前者条件的堆。由堆的定义可以看出，堆顶元素（即第一个元素）必为最大项（大顶堆）。完全二叉树可以很直观地表示堆的结构。堆顶为根，其它为左子树、右子树。初始时把要排序的数的序列看作是一棵顺序存储的二叉树，调整它们的存储序，使之成为一个堆，这时堆的根节点的数最大。然后将根节点与堆的最后一个节点交换。然后对前面(n-1)个数重新调整使之成为堆。依此类推，直到只有两个节点的堆，并对它们作交换，最后得到有n个节点的有序序列。从算法描述来看，堆排序需要两个过程，一是建立堆，二是堆顶与堆的最后一个元素交换位置。所以堆排序有两个函数组成。一是建堆的渗透函数，二是反复调用渗透函数实现排序的函数。 （2）实例： 初始序列：46,79,56,38,40,84 建堆： 交换，从堆中踢出最大数 依次类推：最后堆中剩余的最后两个结点交换，踢出一个，排序完成。 （3）用java实现 66import java.util.Arrays; 67 68public class HeapSort { 69int a[]={49,38,65,97,76,13,27,49,78,34,12,64,5,4,62,99,98,54,56,17,18,23,34,1 5,35,25,53,51}; 70public HeapSort(){ 71heapSort(a); 72} 73public void heapSort(int[] a){ 74System.out.println("开始排序"); 75int arrayLength=a.length; 76//循环建堆 77for(int i=0;i 78//建堆 79 80buildMaxHeap(a,arrayLength-1-i); 81//交换堆顶和最后一个元素 82swap(a,0,arrayLength-1-i); 83System.out.println(Arrays.toString(a)); 84} 85} 86 87private void swap(int[] data, int i, int j) { 88// TODO Auto-generated method stub 89int tmp=data[i]; 90data[i]=data[j]; 91data[j]=tmp; 92} 93//对data数组从0到lastIndex建大顶堆 94private void buildMaxHeap(int[] data, int lastIndex) { 95// TODO Auto-generated method stub 96//从lastIndex处节点（最后一个节点）的父节点开始 97for(int i=(lastIndex-1)/2;i>=0;i--){ 98//k保存正在判断的节点 99int k=i; 100//如果当前k节点的子节点存在 101while(k*2+1<=lastIndex){ 102//k节点的左子节点的索引 103int biggerIndex=2*k+1; 104//如果biggerIndex小于lastIndex，即biggerIndex+1代表的k节点的右子节点存在105if(biggerIndex 106//若果右子节点的值较大 107if(data[biggerIndex] 108//biggerIndex总是记录较大子节点的索引 109biggerIndex++; 110} 111} 112//如果k节点的值小于其较大的子节点的值 113if(data[k] 114//交换他们 115swap(data,k,biggerIndex); 116//将biggerIndex赋予k，开始while循环的下一次循环，重新保证k节点的值大于其左右子节点的值 117k=biggerIndex; 118}else{ 119break; 120} 121} } } } 5.冒泡排序 （1）基本思想：在要排序的一组数中，对当前还未排好序的范围内的全部数，自上而下对相邻的两个数依次进行比较和调整，让较大的数往下沉，较小的往上冒。即：每当两相邻的数比较后发现它们的排序与排序要求相反时，就将它们互换。 （2）实例： （3）用java实现 122public class bubbleSort { 123public bubbleSort(){ 124int a[]={49,38,65,97,76,13,27,49,78,34,12,64,5,4,62,99,98,54,56,17,18,23,34,1 5,35,25,53,51}; 125int temp=0; 126for(int i=0;i 127for(int j=0;j 128if(a[j]>a[j+1]){ 129temp=a[j]; 130a[j]=a[j+1]; 131a[j+1]=temp; 132} 133} 134} 135for(int i=0;i 136System.out.println(a[i]); 137} 138} 139 6.快速排序 （1）基本思想：选择一个基准元素,通常选择第一个元素或者最后一个元素,通过一趟扫描，将待排序列分成两部分,一部分比基准元素小,一部分大于等于基准元素,此时基准元素在其排好序后的正确位置,然后再用同样的方法递归地排序划分的两部分。 （2）实例： （3）用java实现 140public class quickSort { 141int a[]={49,38,65,97,76,13,27,49,78,34,12,64,5,4,62,99,98,54,56,17,18,23,34,1 5,35,25,53,51}; 142public quickSort(){ 143quick(a); 144for(int i=0;i 145System.out.println(a[i]); 146} 147public int getMiddle(int[] list, int low, int high) { 148int tmp = list[low]; //数组的第一个作为中轴 149while(low < high) { 150while (low < high && list[high] >= tmp) { 151 152high--; 153} 154list[low] = list[high]; //比中轴小的记录移到低端 155while(low < high && list[low] <= tmp) { 156low++; 157} 158list[high] = list[low]; //比中轴大的记录移到高端 159} 160list[low] = tmp; //中轴记录到尾 161return low; //返回中轴的位置 162} 163public void_quickSort(int[] list, int low, int high) { 164if (low < high) { 165int middle = getMiddle(list, low, high); //将list数组进行一分为二 166_quickSort(list, low, middle - 1); //对低字表进行递归排序 167_quickSort(list, middle + 1, high); //对高字表进行递归排序 168} 169} 170public void quick(int[] a2) { 171if(a2.length > 0) { //查看数组是否为空 172_quickSort(a2, 0, a2.length - 1); 173} 174} 175} 7、归并排序 （1）基本排序：归并（Merge）排序法是将两个（或两个以上）有序表合并成一个新的有序表，即把待排序序列分为若干个子序列，每个子序列是有序的。然后再把有序子序列合并为整体有序序列。 （2）实例： （3）用java实现 176import java.util.Arrays; 177 178public class mergingSort { 179int a[]={49,38,65,97,76,13,27,49,78,34,12,64,5,4,62,99,98,54,56,17,18,23,34,1 5,35,25,53,51}; 180public mergingSort(){ 181sort(a,0,a.length-1); 182for(int i=0;i 183System.out.println(a[i]); 184} 185public void sort(int[] data, int left, int right) { 186// TODO Auto-generated method stub 187if(left 188//找出中间索引 189int center=(left+right)/2; 190//对左边数组进行递归 191sort(data,left,center); 192//对右边数组进行递归 193sort(data,center+1,right); 194//合并 195merge(data,left,center,right); 196 197} 198} 199public void merge(int[] data, int left, int center, int right) { 200// TODO Auto-generated method stub 201int[] tmpArr=new int[data.length]; 202int mid=center+1; 203//third记录中间数组的索引 204int third=left; 205int tmp=left; 206while(left<=center&&mid<=right){ 207 208//从两个数组中取出最小的放入中间数组 209if(data[left]<=data[mid]){ 210tmpArr[third++]=data[left++]; 211}else{ 212tmpArr[third++]=data[mid++]; 213} 214} 215//剩余部分依次放入中间数组 216while(mid<=right){ 217tmpArr[third++]=data[mid++]; 218} 219while(left<=center){ 220tmpArr[third++]=data[left++]; 221} 222//将中间数组中的内容复制回原数组 223while(tmp<=right){ 224data[tmp]=tmpArr[tmp++]; 225} 226System.out.println(Arrays.toString(data)); 227} 228 229} 8、基数排序 （1）基本思想：将所有待比较数值（正整数）统一为同样的数位长度，数位较短的数前面补零。然后，从最低位开始，依次进行一次排序。这样从最低位排序一直到最高位排序完成以后,数列就变成一个有序序列。 （2）实例： （3）用java实现 230import java.util.ArrayList; 231import java.util.List; 232 233public class radixSort { 234int a[]={49,38,65,97,76,13,27,49,78,34,12,64,5,4,62,99,98,54,101,56,17,18,23, 34,15,35,25,53,51}; 235public radixSort(){ 236sort(a); 237for(int i=0;i 238System.out.println(a[i]); 239} 240public void sort(int[] array){ 241 242//首先确定排序的趟数; 243int max=array[0]; 244for(int i=1;i 245if(array[i]>max){ 246max=array[i]; 247} 248} 249 250int time=0; 251//判断位数; 252while(max>0){ 253max/=10; 254time++; 255} 256 257//建立10个队列; 258List 259for(int i=0;i<10;i++){ 260ArrayList 261queue.add(queue1); 262} 263 264//进行time次分配和收集; 265for(int i=0;i 266 267//分配数组元素; 268for(int j=0;j 269//得到数字的第time+1位数; 270int x=array[j]%(int)Math.pow(10, i+1)/(int)Math.pow(10, i); 271ArrayList 272queue2.add(array[j]); 273queue.set(x, queue2); 274} 275int count=0;//元素计数器; 276//收集队列元素; 277for(int k=0;k<10;k++){ 278while(queue.get(k).size()>0){ 279ArrayList 280array[count]=queue3.get(0); 281queue3.remove(0); 282count++; 283} 284} 285} 286 287} 288 Java实现的几个常用排序算法详细解读 2012-06-27 15:33 easense2009 博客园我要评论(2)字号：T | T 排序算法很多地方都会用到，近期又重新看了一遍算法，并自己简单地实现了一遍，特此记录下来，为以后复习留点材料。废话不多说，下面逐一看看经典的排序算法。 AD：51CTO云计算架构师峰会抢票进行中！ 排序算法很多地方都会用到，近期又重新看了一遍算法，并自己简单地实现了一遍，特此记录下来，为以后复习留点材料。 废话不多说，下面逐一看看经典的排序算法： 1. 选择排序 选择排序的基本思想是遍历数组的过程中，以i 代表当前需要排序的序号，则需要在剩余的[i…n-1] 中找出其中的最小值，然后将找到的最小值与i 指向的值进行交换。因为每一趟确定元素的过程中都会有一个选择最大值的子流程，所以人们形象地称之为选择排序。 举个实例来看看： 1初始： [38, 17, 16, 16, 7, 31, 39, 32, 2, 11] 2 3i = 0: [2 , 17, 16, 16, 7, 31, 39, 32, 38 , 11] (0th [38]<->8th [2]) 4 5i = 1: [2, 7 , 16, 16, 17 , 31, 39, 32, 38, 11] (1st [38]<->4th [17]) 6 7i = 2: [2, 7, 11 , 16, 17, 31, 39, 32, 38, 16 ] (2nd [11]<->9th [16]) 8 9i = 3: [2, 7, 11, 16, 17, 31, 39, 32, 38, 16] ( 无需交换 ) 10 11i = 4: [2, 7, 11, 16, 16 , 31, 39, 32, 38, 17 ] (4th [17]<->9th [16]) 13i = 5: [2, 7, 11, 16, 16, 17 , 39, 32, 38, 31 ] (5th [31]<->9th [17]) 14 15i = 6: [2, 7, 11, 16, 16, 17, 31 , 32, 38, 39 ] (6th [39]<->9th [31]) 16 17i = 7: [2, 7, 11, 16, 16, 17, 31, 32, 38, 39] ( 无需交换 ) 18 19i = 8: [2, 7, 11, 16, 16, 17, 31, 32, 38, 39] ( 无需交换 ) 20 21i = 9: [2, 7, 11, 16, 16, 17, 31, 32, 38, 39] ( 无需交换 ) 由例子可以看出，选择排序随着排序的进行（i 逐渐增大），比较的次数会越来越少，但是不论数组初始是否有序，选择排序都会从i 至数组末尾进行一次选择比较，所以给定长度的数组，选择排序的比较次数是固定的：1 + 2 + 3 + …. + n = n * (n + 1) / 2 ，而交换的次数则跟初始数组的顺序有关，如果初始数组顺序为随机，则在最坏情况下，数组元素将会交换n 次，最好的情况下则可能0 次（数组本身即为有序）。 由此可以推出，选择排序的时间复杂度和空间复杂度分别为O(n2 ) 和O(1) （选择排序只需要一个额外空间用于数组元素交换）。 实现代码： 22/** 23* Selection Sorting 24*/ 25SELECTION(new Sortable() { 26public 28for (int i = 0; i < len; i++) { 29int selected = i; 30for (int j = i + 1; j < len; j++) { 31int compare = array[j].compareTo(array[selected]); 32if (compare != 0 && compare < 0 == ascend) { 33selected = j; 34} 35} 36 37exchange(array, i, selected); 38} 39} 40}) 2. 插入排序 插入排序的基本思想是在遍历数组的过程中，假设在序号i 之前的元素即[0..i-1] 都已 经排好序，本趟需要找到i 对应的元素x 的正确位置k ，并且在寻找这个位置k 的过程 中逐个将比较过的元素往后移一位，为元素x “腾位置”，最后将k 对应的元素值赋为x ，插入排序也是根据排序的特性来命名的。 以下是一个实例，红色标记的数字为插入的数字，被划掉的数字是未参与此次排序的元素，红色标记的数字与被划掉数字之间的元素为逐个向后移动的元素，比如第二趟参与排序的元素为[11, 31, 12] ，需要插入的元素为12 ，但是12 当前并没有处于正确的位 置，于是我们需要依次与前面的元素31 、11 做比较，一边比较一边移动比较过的元素， 直到找到第一个比12 小的元素11 时停止比较，此时31 对应的索引1 则是12 需要插入的位置。 41初始： [11, 31, 12, 5, 34, 30, 26, 38, 36, 18] 42 43第一趟： [11, 31 , 12, 5, 34, 30, 26, 38, 36, 18] （无移动的元素） 44 45第二趟： [11, 12 , 31, 5, 34, 30, 26, 38, 36, 18] （ 31 向后移动） 46 47第三趟： [5 , 11, 12, 31, 34, 30, 26, 38, 36, 18] （ 11, 12, 31 皆向后移动）48 49第四趟： [5, 11, 12, 31, 34 , 30, 26, 38, 36, 18] （无移动的元素） 50 51第五趟： [5, 11, 12, 30 , 31, 34, 26, 38, 36, 18] （ 31, 34 向后移动） 52 53第六趟： [5, 11, 12, 26 , 30, 31, 34, 38, 36, 18] （ 30, 31, 34 向后移动）54 55第七趟： [5, 11, 12, 26, 30, 31, 34, 38 , 36, 18] （无移动的元素） 56 57第八趟： [5, 11, 12, 26, 30, 31, 34, 36 , 38, 18] （ 38 向后移动） 58 59第九趟： [5, 11, 12, 18 , 26, 30, 31, 34, 36, 38] （ 26, 30, 31, 34, 36, 38 向后移动） 插入排序会优于选择排序，理由是它在排序过程中能够利用前部分数组元素已经排好序 的一个优势，有效地减少一些比较的次数，当然这种优势得看数组的初始顺序如何，最坏的情况下（给定的数组恰好为倒序）插入排序需要比较和移动的次数将会等于1 + 2 + 3… + n = n * (n + 1) / 2 ，这种极端情况下，插入排序的效率甚至比选择排序更差。因此插入排序是一个不稳定的排序方法，插入效率与数组初始顺序息息相关。一般情况下，插入排序的时间复杂度和空间复杂度分别为O(n2 ) 和O(1) 。 实现代码： 60/** 61* Insertion Sorting 62*/ 63INSERTION(new Sortable() { 64public 66for (int i = 1; i < len; i++) { 67T toInsert = array[i]; 68int j = i; 69for(; j > 0; j--) { 70int compare = array[j - 1].compareTo(toInsert); 71if(compare == 0|| compare < 0== ascend) { 72break; 73} 74array[j] = array[j - 1]; 75} 76 77array[j] = toInsert; 78} 79} 80}) 3. 冒泡排序 冒泡排序可以算是最经典的排序算法了，记得小弟上学时最先接触的也就是这个算法了，因为实现方法最简单，两层for 循环，里层循环中判断相邻两个元素是否逆序，是的话将两个元素交换，外层循环一次，就能将数组中剩下的元素中最小的元素“浮”到最前面，所以称之为冒泡排序。 照例举个简单的实例吧： 81 82 83初始状态： [24, 19, 26, 39, 36, 7, 31, 29, 38, 23] 84 85内层第一趟： [24, 19, 26, 39, 36, 7, 31, 29, 23 , 38 ] （ 9th [23]<->8th [38 ）86 87内层第二趟： [24, 19, 26, 39, 36, 7, 31, 23 , 29 , 38] （ 8th [23]<->7th [29] ）88 89内层第三趟： [24, 19, 26, 39, 36, 7, 23 , 31 , 29, 38] （ 7th [23]<->6th [31] ）90 91内层第四趟： [24, 19, 26, 39, 36, 7, 23, 31, 29, 38] （ 7 、 23 都位于正确的顺序，无需交换） 92 93内层第五趟： [24, 19, 26, 39, 7 , 36 , 23, 31, 29, 38] （ 5th [7]<->4th [36] ）94 95内层第六趟： [24, 19, 26, 7 , 39 , 36, 23, 31, 29, 38] （ 4th [7]<->3rd [39] ）96 97内层第七趟： [24, 19, 7 , 26 , 39, 36, 23, 31, 29, 38] （ 3rd [7]<->2nd [26] ）98 99内层第八趟： [24, 7 , 19 , 26, 39, 36, 23, 31, 29, 38] （ 2nd [7]<->1st [19] ）100 101内层第九趟： [7 , 24 , 19, 26, 39, 36, 23, 31, 29, 38] （ 1st [7]<->0th [24] ）102 103……… 其实冒泡排序跟选择排序比较相像，比较次数一样，都为n * (n + 1) / 2 ，但是冒泡排序在挑选最小值的过程中会进行额外的交换（冒泡排序在排序中只要发现相邻元素的顺序不对就会进行交换，与之对应的是选择排序，只会在内层循环比较结束之后根据情况决定是否进行交换），所以在我看来，选择排序属于冒泡排序的改进版。 实现代码： 104/** 105* Bubble Sorting, it's very similar with Insertion Sorting 106*/ 107BUBBLE(new Sortable() { 108public 110int lastExchangedIdx = 0; 111for(int i = 0; i < length; i++) { 112// mark the flag to identity whether exchange happened to false 113boolean isExchanged = false; 114// last compare and exchange happened before reaching index i 115int currOrderedIdx = lastExchangedIdx > i ? lastExchangedIdx : i; 116for (int j = length - 1; j > currOrderedIdx; j--) { 一道常考的javaSE面试题 上周一,.NET班有四个同学去面试，面试题是一道排序题，不管用什么方式做出结果就行。 就这道题我也想些想法，当时他们和我说完，我在想用什么方法可以实现。毕竟现在javaSE都忘的差不多了，现在主要学的还是javaEE方面。年前学习JSP和SERVLET一片的知识，到了年后主要学习三大框架、ajax、jquery和XML等。不过当时出现脑中的算法只有：java.util包中定义的Arrays类和冒泡法。 下面就拿上面方说的那两种方法具体说说。 在JDK的java.util包中定义的Arrays类提供了多种数据操作方法，实现了对数组元素的排序、填充、转换、增强检索和深度比较等功能，所以的这些方法都是static的，下面介绍对数组元素进行排序的方法。数组元素的排序通常是指一维数值型数组元素按升序排序，偶尔也会涉及一维String数组排序，一般来说，多维和其他引用类型的元素数组排序使用意义不大。 Arrays类中的sort()的格式： public static void sort([] a); 案例1： JDK的java.util包中定义的Arrays类提供了排序方法 一维数组排序： Java代码 1.package cn.z_xiaofei168.sort; 2. 3.import java.util.Arrays; 4. 5.public class TestArraySort { 6. 7./** 8. * @author z_xiaofei168 9. */ 10.public static void main(String[] args) { 11.int[] arr = { -1, -3, 5, 7, 9, 2, 4, 6, 8, 10 }; 12. System.out.print("整数排序前："); 13. displayIntArr(arr); 14. Arrays.sort(arr); 15. System.out.print("整数排序后："); 16. displayIntArr(arr); 17. Java程序员必知的8大排序<合肥软件培训> [来源：本站| 日期：2012年12月24日| 浏览173次] 字体:[大中小] 8种排序之间的关系: 1，直接插入排序 （1）基本思想：在要排序的一组数中，假设前面(n-1)[n>=2] 个数已经是排好顺序的，现在要把第n个数插到前面的有序数中，使得这n个数 也是排好顺序的。如此反复循环，直到全部排好顺序。 （2）实例 （3）用java实现 //从小到大 package com.njue; 2 3public class insertSort { 4public insertSort(){ 5 inta[]={49,38,65,97,76,13,27,49,78,34,12,64,5,4,62,99,98,54,56,17,18,23,34,15,35,25,53,51}; 6int temp=0; 7for(int i=1;i package java项目; public class X{ public static void main(String[] args) { inti,j,t,k; final int M=100000; int []a=new int[M]; System.out.println("随机数:"); for(i=0;i package com.scott.util; import java.io.*; import java.util.ArrayList; import https://www.wendangku.net/doc/fb12686894.html,parator; import java.util.Iterator; import java.util.List; /** * Created by Scott on 2017/11/1. */ public class LargeFileDataSort { // 测试大文件路径 public final static String testFilePath = "E:/dataTest/largeFileData.txt"; public final static String resultFilePath = "E:/dataTest/largeFileResult.txt"; // 切分大文件的小文件大小MB, 默认为100MB private final static int size = 200; private static int byteSize = size * 1024 * 1024; public static void main(String[] args) throws IOException { // 生成测试文件 createTestData(); Long start = System.currentTimeMillis(); work(); Long end = System.currentTimeMillis(); System.out.println((end - start) / 1000/ 60); } /** * 切分文件每份大小 */ public static void work() throws IOException { File file = new File(testFilePath); if (!file.exists()) { return; } // 2.1 得到文件大小MB double mbsize = file.length() / 1024 / 1024; // 2.2 计算得到切分的文件数 double fileNum = Math.ceil(mbsize / size); // 2.3 临时文件 List java程序员应该掌握哪些排序算法?排序大的分类可以分为两种：内排序和外排序。在排序过程中，全部记录存放在内存，则称为内排序，如果排序过程中需要使用外存，则称为外排序。下面讲的排序都是属于内排序。在java的学习中，身为程序员的我们需要掌握以下八大排序算法。 1、直接插入排序 在要排序的一组数中，假设前面(n-1)[n>=2] 个数已经是排好顺序的，现在要把第n个数插到前面的有序数中，使得这n个数也是排好顺序的。如此反复循环，直到全部排好顺序。 2、希尔排序(最小增量排序) 算法先将要排序的一组数按某个增量d(n/2,n为要排序数的个数)分成若干组，每组中记录的下标相差d.对每组中全部元素进行直接插入排序，然后再用一个较小的增量(d/2)对它进行分组，在每组中再进行直接插入排序。当增量减到1 时，进行直接插入排序后，排序完成。 3、简单选择排序 在要排序的一组数中，选出最小的一个数与第一个位置的数交换;然后在剩下的数当中再找最小的与第二个位置的数交换，如此循环到倒数第二个数和最后一个数比较为止。 4、堆排序 堆排序是一种树形选择排序，是对直接选择排序的有效改进。堆的定义如下：具有n 个元素的序列(h1,h2,...,hn),当且仅当满足(hi>=h2i,hi>=2i+1)或(hi<=h2i,hi<=2i+1)(i=1,2,...,n/2)时称之为堆。在这里只讨论满足前者条件的堆。由堆的定义可以看出，堆顶元素(即第一个元素)必为最大项(大顶堆)。完全二叉树可以很直观地表示堆的结构。堆顶为根，其它为左子树、右子树。初始时把要排序的数的序列看作是一棵顺序存储的二叉树，调整它们的存储序，使之成为一个堆，这时堆的根节点的数最大。然后将根节点与堆的最后一个节点交换。然后对前面(n-1)个数重新调整使之成为堆。依此类推，直到只有两个节点的堆，并对它们作交换，最后得到有n个节点的有序序列。从算法描述来看，堆排序需要两个过程，一是建立堆，二是堆顶与堆的最后一个元素交换位置。所以堆排序有两个函数组成。一是建堆的渗透函数，二是反复调用渗透函数实现排序的函数。 5、冒泡排序 在要排序的一组数中，对当前还未排好序的范围内的全部数，自上而下对相邻的两个数依次进行比较和调整，让较大的数往下沉，较小的往上冒。即：每当两相邻的数比较后发现 java的几种排序方式 用Java语言实现的各种排序，包括插入排序、冒泡排序、选择排序、Shell排序、快速排序、归并排序、堆排序、SortUtil等。 插入排序： package org.rut.util.algorithm.support; import org.rut.util.algorithm.SortUtil; /** * @author treeroot * @since 2006-2-2 * @version 1.0 */ public class InsertSort implements SortUtil.Sort{ /* (non-Javadoc) * @see org.rut.util.algorithm.SortUtil.Sort#sort(int[]) */ public void sort(int[] data) { int temp; for(int i=1;i for(int j=i;(j>0)&&(data[j] SortUtil.swap(data,j,j-1); } } } } 冒泡排序： package org.rut.util.algorithm.support; import org.rut.util.algorithm.SortUtil; /** * @author treeroot * @since 2006-2-2 * @version 1.0 */ public class BubbleSort implements SortUtil.Sort{ /* (non-Javadoc) * @see org.rut.util.algorithm.SortUtil.Sort#sort(int[]) */ public void sort(int[] data) { int temp; for(int i=0;i for(int j=data.length-1;j>i;j--){ if(data[j] SortUtil.swap(data,j,j-1); } } } } } 选择排序： 一、插入排序 1、基本思想 插入排序（以升序为例）的基本操作是将一个数插入到一个已经排好序的数据序列中，插入后的数据序列是有序的并且元素个数加一。插入排序的主要思想是： 假设要排序的数组为A[]元素个数为n，将这个数组分为两个部分前n-1个元素和最后一个元素，将最后一个元素插入到已经排好序的n-1个元素中的合适的位置。 InsertSort(A[n]) //对A[n]进行插入排序 { for i=1 to n divide(A[i-1],a[i]) //将A[i]分为两部分，前i-1个元素和最后一个元素 Insert(a[i],A[i-1])//将最后一个元素插入到排好序的前i-1个元素中 } 2、算法复杂度分析 插入排序存在着最好情况和最坏情况，最好的情况是已经是排好序的了，这时只需比较n-1次即可；最坏的情况是序列是降序的需要排成升序的，那么此时就需要比较n(n-1)/2。插入排序的赋值操作是比较操作的次数加上n-1次。平均来说插入排序的算法复杂度为O(n2)。 3、编程实现 public static void InsertSort(int[] A){ for(int i=1;i package help; import java.util.Scanner; /** * * @author ben */ public class Help { /** * @param args the command line arguments */ public static void main(String[] args) { // TODO code application logic here int num[] = new int[11]; int num2[] = new int[11]; int max; int number = 0; int help; Scanner scanner = new Scanner(System.in); System.out.println("请输入十组数据："); for(int x=1;x<=10;x++) { num2[x]=num[x]=scanner.nextInt(); } for(int m=1;m<=10;m++) { max=num[m]; for(int n=m;n<=10;n++) { if(num[n]>=max) { max=num[n]; number=n; } } help=num[number]; num[number]=num[m]; num[m]=help; } System.out.println("排序后的数组（由大到小）"); for(int y=1;y<=10;y++) { System.out.print(num[y]+""); } System.out.println("\n原来的数组"); for(int y=1;y<=10;y++) { System.out.print(""+num2[y]); } } } Java程序员必知的8大排序(上) 本文主要详解了Java语言的8大排序的基本思想以及实例解读，详细请看下文 AD：8种排序之间的关系: 1，直接插入排序 （1）基本思想：在要排序的一组数中，假设前面(n-1)[n>=2] 个数已经是排 好顺序的，现在要把第n个数插到前面的有序数中，使得这n个数 也是排好顺序的。如此反复循环，直到全部排好顺序。 （2）实例 （3）用java实现 1package com.njue; 2 3public class insertSort { 4public insertSort(){ 5 inta[]={49,38,65,97,76,13,27,49,78,34,12,64,5,4,62,99,98,54,56,17,18,23,3 4,15,35,25,53,51}; 6int temp=0; 7for(int i=1;i 冒泡排序法 1.public class SortArray_01 { 2. public static void main(String args[]) { 3. int[] array = { 14, 5, 86, 4, 12, 3, 21, 13, 11, 2, 55 }; // 创建一个初始化的一维数组array 4. System.out.println("未排序的数组:"); 5. for (int i = 0; i < array.length; i++) { // 遍历array数组中的元素 6. System.out.print(" " + array[i]); // 输出数组元素 7. if ((i + 1) % 5 == 0) // 每5个元素一行 8. System.out.println(); 9. } 10. int mid; // 定义一个中间变量， 起到临时存储数据的作用 11. for (int i = 0; i < array.length; i++) { // 执行冒 泡排序法 12. for (int j = i; j < array.length; j++) { 13. if (array[j] < array[i]) { 14. mid = array[i]; 15. array[i] = array[j]; 16. array[j] = mid; 17. } 18. } 19. } 20. System.out.println("\n使用冒泡法排序后的数组:"); 21. for (int i = 0; i < array.length; i++) { // 遍历排好序的array数组中的元素 22. System.out.print(" " + array[i]); // 输出数组元素 23. if ((i + 1) % 5 == 0) 24. System.out.println(); // 每5 个元素一行 25. } 26. } 27.} 数组递增排序 JAVA中在运用数组进行排序功能时，一般有四种方法：快速排序法、冒泡法、选择排序法、插入排序法。 快速排序法主要是运用了Arrays中的一个方法Arrays.sort（）实现。 冒泡法是运用遍历数组进行比较，通过不断的比较将最小值或者最大值一个一个的遍历出来。 选择排序法是将数组的第一个数据作为最大或者最小的值，然后通过比较循环，输出有序的数组。 插入排序是选择一个数组中的数据，通过不断的插入比较最后进行排序。下面我就将他们的实现方法一一详解供大家参考。 <1>利用Arrays带有的排序方法快速排序 import java.util.Arrays; publicclass Test2{ publicstaticvoid main(String[] args){ int[] a={5,4,2,4,9,1}; Arrays.sort(a); //进行排序 for(int i: a){ System.out.print(i); } } } <2>冒泡排序算法 publicstaticint[] bubbleSort(int[] args){//冒泡排序算法 for(int i=0;i 此文中的七种排序算法为个人总结，程序均在eclipse中验证成功，可供参考 package sort; /* * 各种排序方法总结 */ public class Sort { public static void main(String[] args) { int[] array={4,9,6,7,2,3,1,5,8,0}; Sort.heapSort(array); for(int i=0;i Java程序员必知的8大排序本文主要详解了Java语言的8大排序的基本思想以及实例解读，详细请看下文8种排序之间的关系: 1，直接插入排序 （1）基本思想：在要排序的一组数中，假设前面(n-1)[n>=2] 个数已经是排 好顺序的，现在要把第n个数插到前面的有序数中，使得这n个数 也是排好顺序的。如此反复循环，直到全部排好顺序。 （2）实例 （3）用java实现 1.package com.njue; 2. 3.public class insertSort { 4.public insertSort(){ 5. inta[]={49,38,65,97,76,13,27,49,78,34,12,64,5,4,62,99,98,54,56,17, 18,23,34,15,35,25,53,51}; 6.int temp=0; 7.for(int i=1;i ** 大家好，我现在正在学习，虽然在这之前我已经学习过一遍了，但是现在再重新来学，才发现以前学地太肤浅了，而且学地质量也很不好，所以，现在我又重新站在了新地起跑线上，开始了我地学习之旅，喜欢地朋友和想学习地朋友来和我一起前进吧.我会及时地把自己学地一些东西总结出来，并传送到文库中和大家一起分享地. 所以地时候到了，，！ （我地号，愿意交流地同学可以加我呦) 中地几种排序方法：冒泡排序，选择排序，插入排序和快速排序.下面是我当初开始学时地一些源代码，简单易懂，拿出来分享给大家，希望对刚接触地人能够有所帮助.b5E2R。 在此，也和大家共勉一下：相信自己，用心学习，大胆创新！ * .*首先是冒泡排序，冒泡排序地思想是：数组中地相邻地两个数进行比较，如果后面地数比前面地数大，则两个数进行交换，每完成一次循环，最大地那个数就排在了最后面；以此类推，在第次循环后，数组中地个数就排好了.下面是源代码p1Ean。 * { ([] ){ [] {}; ( <){ ([]); } ( <){ ( <){ ([]<[]){ []; [][]; []; } } } (); ( <){ ([]); } } } *.其次是选择排序.选择排序地思想是记录下数组中最小地那个数地下标，然后与第一个数进行交换，以此类推，直到 排好序为止.下面是源代码DXDiT。* { ([] ){ [] {}; ( <){ ([]); } 排序 ( <){ (); (); } (); ( <){ ([]); } } 找到最小地数地下标 ([] ){ []; ; ( <){ ([]<){ []; ; } } ; } 两个数进行交换 ([] ){ []; [][]; []; } } *.然后是插入排序.插入排序地基本思想是：新建一个数组，将需要排序地数组地第一个元素先放到新数组中去，然后把剩下地元素有序地、依次插入到新数组中去.下面是源代码RTCrp。 * { ([] ){ [] {}; Java排序算法 1）分类： 1）插入排序（直接插入排序、希尔排序） 2）交换排序（冒泡排序、快速排序） 3）选择排序（直接选择排序、堆排序） 4）归并排序 5）分配排序（箱排序、基数排序） 所需辅助空间最多：归并排序 所需辅助空间最少：堆排序 平均速度最快：快速排序 不稳定：快速排序，希尔排序，堆排序。 1）选择排序算法的时候 1.数据的规模； 2.数据的类型； 3.数据已有的顺序 一般来说，当数据规模较小时，应选择直接插入排序或冒泡排序。任何排序算法在数据量小时基本体现不出来差距。考虑数据的类型，比如如果全部是正整数，那么考虑使用桶排序为最优。考虑数据已有顺序，快排是一种不稳定的排序（当然可以改进），对于大部分排好的数据，快排会浪费大量不必要的步骤。数据量极小，而起已经基本排好序，冒泡是最佳选择。我们说快排好，是指大量随机数据下，快排效果最理想。而不是所有情况。 3）总结： ——按平均的时间性能来分： 1）时间复杂度为O(nlogn)的方法有：快速排序、堆排序和归并排序，其中以快速排序为最好； 2）时间复杂度为O(n2)的有：直接插入排序、起泡排序和简单选择排序，其中以直接插入为最好，特别是对那些对关键字近似有序的记录序列尤为如此； 3）时间复杂度为O(n)的排序方法只有，基数排序。 当待排记录序列按关键字顺序有序时，直接插入排序和起泡排序能达到O(n)的时间复杂度;而对于快速排序而言，这是最不好的情况，此时的时间性能蜕化为O(n2)，因此是应该尽量避免的情况。简单选择排序、堆排序和归并排序的时间性能不随记录序列中关键字的分布而改变。 ——按平均的空间性能来分（指的是排序过程中所需的辅助空间大小）： 1）所有的简单排序方法(包括：直接插入、起泡和简单选择)和堆排序的空间复杂度为O(1)； 2）快速排序为O(log n )，为栈所需的辅助空间; 3）归并排序所需辅助空间最多，其空间复杂度为O(n ); 4）链式基数排序需附设队列首尾指针，则空间复杂度为O(rd )。 ——排序方法的稳定性能： 1）稳定的排序方法指的是，对于两个关键字相等的记录，它们在序列中的相对位置，在排序之前和经过排序之后，没有改变。 2）当对多关键字的记录序列进行LSD方法排序时，必须采用稳定的排序方法。 3）对于不稳定的排序方法，只要能举出一个实例说明即可。 4）快速排序，希尔排序和堆排序是不稳定的排序方法。 4）插入排序： 包括直接插入排序，希尔插入排序。 直接插入排序：将一个记录插入到已经排序好的有序表中。 1, sorted数组的第0个位置没有放数据。 java中常用的七大排序算法 这段时间闲了下来，就抽了点时间总结了下java中常用的七大排序算法，希望以后可以回顾！ 1.插入排序算法 插入排序的基本思想是在遍历数组的过程中，假设在序号i之前的元素即[0..i-1] 都已经排好序，本趟需要找到i对应的元素x 的正确位置k ，并且在寻找这个位置k 的过程中逐个将比较过的元素往后移一位，为元素x “腾位置”，最后将k 对应的元素值赋为x ，一般情况下，插入排序的时间复杂度和空间复杂度分别为O(n2) 和O(1)。 /** * @paramint[] 未排序数组 * @return int[] 排完序数组 */ publicint[] sortInsert(int[] array){ for(inti=1;i public class PaiXu{ /** * @author zongyanshan * @since 20130725 */ public static void main(String[] args) { // TODO Auto-generated method stub int[] num = { 2, 9, 3, 1, 7, 4 }; // PopSortTest.popSort(num); // PopSortTest.chioseSort(num); // PopSortTest.insertSort(num); PopSortTest.shellSort(num); for (int i = 0; i < num.length; i++) { System.out.println(num[i]); } } // 冒泡排序法 public static int[] popSort(int num[]) { int temp; for (int i = 0; i < num.length; i++) { for (int j = 0; j < num.length - 1; j++) { temp = num[j]; if (num[j + 1] > num[j]) { num[j] = num[j + 1]; num[j + 1] = temp; } } } return num; } // 选择排序法 public static void choiceSort(int num[]) { int temp = 0; for (int i = 0; i < num.length; i++) { for (int j = i; j < num.length - 1; j++) { temp = num[i]; if (num[j + 1] > temp) { int temp2 = temp; temp = num[j + 1]; num[j + 1] = temp2; } 以下内容节选自Java私塾自编经典教材： 下面是Java实现的一些常见排序算法。 1：冒泡排序 对几个无序的数字进行排序，比较常用的方法是冒泡排序法。冒泡法排序是一个比较简单的排序方法，在待排序的数列基本有序的情况下排序速度较快。 基本思路：对未排序的各元素从头到尾依次比较相邻的两个元素是否逆序（与欲排顺序相反），若逆序就交换这两元素，经过第一轮比较排序后便可把最大（或最小）的元素排好，然后再用同样的方法把剩下的元素逐个进行比较，就得到了你所要的顺序。 可以看出如果有N个元素，那么一共要进行N-1轮比较，第I轮要进行N-I次比较。（如：有5个元素，则要进行5-1轮比较。第3轮则要进行5-3次比较） 示例如下： public class Test { public static void main(String[] args) { //需要排序的数组，目前是按照升序排列的 int a[] = new int[5]; a[0] = 3; a[1] = 4; a[2] = 1; a[3] = 5; a[4] = 2; //冒泡排序 for(int i=0;i 六归并排序 算法思想是每次把待排序列分成两部分，分别对这两部分递归地用归并排序，完成后把这两个子部分合并成一个 序列。 归并排序借助一个全局性临时数组来方便对子序列的归并，该算法核心在于归并。 package algorithms; import https://www.wendangku.net/doc/fb12686894.html,ng.reflect.Array; /** * @author yovn * */ public class MergeSorter merge_sort(array,middle+1,to,temporary); merge(array,from,to,middle,temporary); } private final void merge(E[] array, int from, int to, int middle, E[] temporary) { int k=0,leftIndex=0,rightIndex=to-from; System.arraycopy(array, from, temporary, 0, middle-from+1); for(int i=0;i 一、选择题 1．某内排序方法的稳定性是指( )。 A．该排序算法不允许有相同的关键字记录B．该排序算法允许有相同的关键字记录 C．平均时间为0（n log n）的排序方法D．以上都不对 2．下面给出的四种排序法中( )排序法是不稳定性排序法。 A. 插入 B. 冒泡 C. 二路归并 D. 堆积 3．下列排序算法中，其中（）是稳定的。 A. 堆排序，冒泡排序 B. 快速排序，堆排序 C. 直接选择排序，归并排序 D. 归并排序，冒泡排序 4．稳定的排序方法是（） A．直接插入排序和快速排序B．折半插入排序和起泡排序 C．简单选择排序和四路归并排序D．树形选择排序和shell排序 5．下列排序方法中，哪一个是稳定的排序方法？（） A．直接选择排序B．二分法插入排序C．希尔排序D．快速排序 6．若要求尽可能快地对序列进行稳定的排序，则应选（A．快速排序B．归并排序C．冒泡排序）。 7．如果待排序序列中两个数据元素具有相同的值，在排序前后它们的相互位置发生颠倒，则称该排序算法是 不稳定的。（）就是不稳定的排序方法。 A．起泡排序B．归并排序C．Shell排序D．直接插入排序E．简单选择排序8．若要求排序是稳定的，且关键字为实数，则在下列排序方法中应选（）排序为宜。 A．直接插入B．直接选择C．堆D．快速E．基数 9．若需在O(nlog2n)的时间内完成对数组的排序，且要求排序是稳定的，则可选择的排序方法是（）。 A. 快速排序 B. 堆排序 C. 归并排序 D. 直接插入排序 10．下面的排序算法中，不稳定的是（） A.起泡排序 B.折半插入排序 C.简单选择排序 D.希尔排序 E.基数排序 F.堆排序。 11．下列内部排序算法中： A．快速排序B.直接插入排序C. 二路归并排序D. 简单选择排序E. 起泡排序F. 堆排序（1）其比较次数与序列初态无关的算法是（）（2）不稳定的排序算法是（） （3）在初始序列已基本有序（除去n个元素中的某k个元素后即呈有序，k<java 排序面试题
排序算法原理与实现(java)
java比较两种排序的优劣
JAVA实现大文件排序
java程序员需掌握这八大排序算法
java的几种排序方式
java中的各种排序案例
用java写的选择排序 (由大到小)
Java程序员必知的8大排序(上)
JAVA数组的排序方法实例
JAVA中运用数组的四种排序方法
java的七种经典排序
java中8大排序方法
java中几种简单的排序
Java各种排序算法
java中常用的七大排序算法
用java编写的排序程序
Java实现的常见排序算法
Java排序算法
Java排序选择题
- JAVA实现几种常见排序方法 直插、冒泡、选择、快排、堆排等
- JAVA实现大文件排序
- 用java写的选择排序 (由大到小)
- JAVA堆排序和几种排序方法实现代码
- Java实现的常见排序算法
- JAVA常用4种排序方法
- java常用排序算法
- JAVA中运用数组的四种排序方法
- 几种常见排序算法(JAVA实现)
- java排序算法大全
- java比较两种排序的优劣
- Java程序员必知的8大排序及详解
- java中的各种排序案例
- java中几种简单的排序
- 用java编写的排序程序
- 常用排序算法总结(含Java代码)
- java 对数值进行排序
- JAVA数组的排序方法实例
- Java各种排序算法
- Java排序选择题