java 排序算法

一.冒泡排序

特点:实现简单,无额外空间消耗,速度较慢,适合数据较少的场景,复杂度为O(N^2)

思路:每一轮比较都从头开始,然后两两比较,如果左值比右值大,则交换位置,每一轮结束后,当前轮"最后一个元素"必将是最大的.

 

场景：算法稳定，数据量较小的场景。时间复杂度O(n^2)

 

Java代码  

  1. 原始数组：[4,3,10,6,2]  
  2. 过程：每一次遍历，都会将“无序区”中最大的元素交换到数组的末尾  
  3. ------------>  
  4. -->3,4,10,6,2  
  5. -->3,4,10,6,2  
  6. -->3,4,6,10,2  
  7. -->3,4,6,2,[10]  
  8. ------------>  
  9. -->3,4,6,2,[10]  
  10. -->3,4,6,2,[10]  
  11. -->3,4,2,[6,10]  
  12. ------------>  
  13. -->3,4,2,[6,10]  
  14. -->3,2,[4,6,10]  
  15. ------------>  
  16. -->2,[3,4,6,10]  
  17. ---->  
  18. 结束：[2,3,4,6,10]  

 

Java代码  

  1. public class BubbleSort {  
  2.   
  3.     static void sort(int[] sources){  
  4.         int tmp;  
  5.         int size = sources.length;  
  6.         for(int i =0; i < size - 1; i++){  
  7.             //精髓:每次遍历,都将"最大"元素顶到最后  
  8.             //0, 1,8,13,3,4,7,||20  
  9.             //0, 1,8,3,4,7,|| 13,20  
  10.             //0, 1,3,4,7,||8,13,20  
  11.             //0 ,1,3,4|| 7,8,13,20  
  12.             for(int j=0; j< size -i -1;j++){  
  13.                 if(sources[j] > sources[j+1]){  
  14.                     tmp = sources[j];  
  15.                     sources[j] = sources[j+1];  
  16.                     sources[j+1] = tmp;  
  17.                 }  
  18.             }  
  19.         }  
  20.     }  
  21.     /** 
  22.      * @param args 
  23.      */  
  24.     public static void main(String[] args) {  
  25.         int[] sources = {1,0,20,8,13,3,4,7};  
  26.         sort(sources);  
  27.         System.out.println(Arrays.toString(sources));  
  28.   
  29.     }  
  30.   
  31. }  

 

二.快速排序

特点:速度快,无额外空间开支,不过算法本身基于递归,可能对内存有额外的消耗.不适合数据集合较大的场景.

思路:就像对班级中的同学根据身高分组一样,首先找个学生做"标杆",比他高的站后面,比他矮的站前面;然后从此"标杆"之前/之后的队列中,分别再在找一个"标杆",并按照相同的规则排队,直到结束!!"标杆"的选取,可以是随机的.下面的例子中,将指定数组"区间"(low~high)的一个元素(即low)作为"标杆".

 

场景：算法不稳定，时间复杂度O(n*logn),空间复杂度O(n*logn)

Java代码  

  1. 原始数组：[4,3,10,6,2]  
  2. 过程：每次递归内的排序，总是先选择“标杆”,我们取递归区间的第一个元素为标杆  
  3. ------------>  
  4. --->标杆为4,右边开始交换,将比4小的交换  
  5. --->2,3,10,6,[4]  
  6. --->标杆为4,左边开始交换，将比4大的交换  
  7. --->2,3,[4],6,10  
  8.   
  9. ------------>  
  10. ---->[4]的左右两边分别递归，分成2部分  
  11. (递归1),标杆为2  
  12. ---->2,[3]  
  13. (递归2),标杆为6  
  14. ---->[6],10  
  15.   
  16. ....  
  17. 结束：[2,3,4,6,10]  

 

Java代码  

  1. public class QuickSort {  
  2.   
  3.     public static void sort(int[] sources,int low,int high){  
  4.         if(low < high){  
  5.             int key = sources[low];//此轮比较的key,左边比key大,右边比key小.  
  6.             int l = low;  
  7.             int h = high;  
  8.             int tmp;  
  9.             while(l < h){  
  10.                 //因为我们不能创建额外的数组,所以才取了"交换"数据的方式.  
  11.                 //从右边开始,将比key大的交换到过来.  
  12.                 while(l < h && sources[h] >= key){  
  13.                     h--;  
  14.                 }  
  15.                 //右边找到了比key大的.  
  16.                 if(l < h){  
  17.                     //交换顺序  
  18.                     tmp = sources[l];  
  19.                     sources[l] = sources[h];  
  20.                     sources[h] = tmp;  
  21.                 }  
  22.                 //从左边开始,将比key小的交换过来  
  23.                 while(l < h && sources[l] <= key){  
  24.                     l++;  
  25.                 }  
  26.                 if(l < h){  
  27.                     tmp = sources[l];  
  28.                     sources[l] = sources[h];  
  29.                     sources[h] = tmp;  
  30.                 }  
  31.             }  
  32.             sort(sources, low, l-1);  
  33.             sort(sources, l+1, high);  
  34.         }  
  35.     }  
  36.     /** 
  37.      * @param args 
  38.      */  
  39.     public static void main(String[] args) {  
  40.         int[] sources = {2,15,3,100,87,-1,34,25,77,80,62,11,7,2,55,22};  
  41.         sort(sources, 0, sources.length -1);  
  42.         System.out.println(Arrays.toString(sources));  
  43.   
  44.     }  
  45.   
  46. }  

 

三.归并排序

特点: 速度快,不过需要额外的一些存储空间(存储当前递归中有序区),内部基于递归,不适合数据量较大的场景.

思路:分治法,将数组逐步拆分为"组",直到最小的"组",然后每个组内排序,然后依次和相邻的组"排序合并",其中"排序".其内部排序非常简单.直接比较.

 

场景：算法稳定，适合元素个数较多时，时间复杂度O(n*logn),空间复杂度O(1)

Java代码  

  1. 原始数组：[4,3,10,6,2]  
  2. 过程：首先将原始数组拆分为更小的组，然后一次对“组”进行排序  
  3. ------------>  
  4. --->拆分  
  5.              [4,3,10,6,2]  
  6.                   |  
  7.         [4,3]     [10,6,2]  
  8.           |           |  
  9.            
  10.        [4],[3]   [10,6],[2]  
  11.           |           |  
  12.        [4],[3]   [10],[6],[2]  
  13. --->合并与排序，从底部开始(递归中)  
  14.        [4],[3]   [10],[6],[2]  
  15.           |           |  
  16.         [3,4]     [6,10],[2]  
  17.           |           |  
  18.         [3,4]      [2,6,10]  
  19.                 |  
  20.            [2,3,4,6,10]  
  21. ....  
  22. 结束：[2,3,4,6,10]  

 

Java代码  

  1. public class MergeSort {  
  2.     /** 
  3.      * 对指定区间的数据进行排序,将begin~end之间的数据分成两部分 
  4.      * @param sources 
  5.      * @param begin 
  6.      * @param end 
  7.      */  
  8.     public static void sort(int[] sources,int begin,int end){  
  9.         if(begin < end){  
  10.             int range = end - begin;  
  11.             int mid = begin + range/2;  
  12.             sort(sources,begin,mid);//左段  
  13.             sort(sources,mid + 1,end);//右端  
  14.             merge(sources, begin, mid, end);  
  15.         }  
  16.     }  
  17.       
  18.     /** 
  19.      * 对begin~mid,mid+1 ~end两段区间中的数据进行排序并合并 
  20.      * @param sources 
  21.      * @param begin 
  22.      * @param mid 
  23.      * @param end 
  24.      */  
  25.     private static void merge(int[] sources,int begin,int mid,int end){  
  26.         int[] tmp = new int[end - begin + 1];  
  27.         int b1 = begin;  
  28.         int e1 = mid;  
  29.         int b2 = mid+1;  
  30.         int e2 = end;  
  31.         int i=0;  
  32.         for(;b1 <= e1 && b2 <= e2 ; i++){  
  33.             //填充tmp数组,并依此在两段数据区域中找到最小的  
  34.             if(sources[b1] <= sources[b2]){  
  35.                 tmp[i] = sources[b1];  
  36.                 b1++;  
  37.             }else{  
  38.                 tmp[i] = sources[b2];  
  39.                 b2++;  
  40.             }  
  41.         }  
  42.         //到此为止,两段数据区域,已经至少一个被扫描完毕  
  43.         if(b1 > e1){  
  44.             //如果b1~e1扫描完毕,那么可能b2~e2还有剩余  
  45.             for(int t = b2;t < e2 + 1; t++){  
  46.                 tmp[i] = sources[t];  
  47.                 i++;  
  48.             }  
  49.         }  
  50.         if(b2 > e2){  
  51.             //如果b2~e2扫描完毕,那么可能b1~e1还有剩余  
  52.             for(int t = b1;t < e1 + 1; t++){  
  53.                 tmp[i] = sources[t];  
  54.                 i++;  
  55.             }  
  56.         }  
  57.         //replace and fill:将tmp数组的数据,替换到source中,begin~end  
  58.         //因为此时tmp中的数据是排序好的  
  59.         i=0;  
  60.         for(int t= begin;t <= end; t++){  
  61.             sources[t] = tmp[i];  
  62.             i++;  
  63.         }  
  64.         tmp = null;//  
  65.     }  
  66.       
  67.     /** 
  68.      * @param args 
  69.      */  
  70.     public static void main(String[] args) {  
  71.         int[] sources = {1,0,20,8,13,3,4,7,-1};  
  72.         sort(sources,0,sources.length -1 );  
  73.         System.out.println(Arrays.toString(sources));  
  74.   
  75.     }  
  76.   
  77. }  

 

四.堆排序

特点:速度快,适合大数据量排序,无额外空间消耗,

思路: 将原始数据看做一个"二叉树",首先构建一个"大顶堆":从最后一个(层)非叶子节点开始倒序遍历整个树,依次比较当前节点和它的左右子节点的大小,将较大的值和当前节点交换,树遍历结束后,那么树的根(堆顶)肯定是数组中最大的元素.这个过程称为"构建初始堆".

    当"初始堆"构建完毕,最大的元素放在了"堆顶",将"堆顶"的元素和数组的最后一个元素交换,由此可见,数组的最后元素在此后的排序中,已经不需要参与了.那么剩余的元素集合,就是"无序区域".

    接下来,对"无序区域"的排序方式和构建"初始堆"过程一样.直到整个"树"被遍历结束.

 

场景：算法不稳定，适合元素个数较多时，时间复杂度O(n*logn),空间复杂度O(1)

Java代码  

  1. 原始数组：[4,3,10,6,2,1]  
  2. 过程：首先构建一次“初始堆”，然后基于“初始堆”进行“交换”  
  3. ------------->按照元素顺序，构建成树  
  4.           [4]  
  5.        |       |  
  6.      [3]      [10]  
  7.       |         |  
  8.    [6] [2]     [1]  
  9. -------------->初始堆，从树的叶子节点开始向上进行，最终需要将最大的元素，交换到“顶”部  
  10. -------------->每个节点都和其左右子节点进行比较，将最大的元素，和当前节点交换,如果交换过程中,有打破"大顶堆"原则,将递归.  
  11. ++++++++++++++  
  12.           [4]  
  13.        |       |  
  14.      [6]      [10]  
  15.       |         |  
  16.    [3] [2]     [1]  
  17. 因为[6],[3],[2]中，6最大，因此6需要和3交换位置。至此，[3],[10]两个节点已经肃清  
  18. ++++++++++++++  
  19.           [10]  
  20.        |       |  
  21.      [6]      [4]  
  22.       |         |  
  23.    [3] [2]     [1]  
  24. 因为在[4],[6],[10]中，10最大，因此4需要和10交换位置；此过程依次进行，直到根节点。  
  25. 到此为止数组为[10,6,4,3,2,1],全部为“无序区”  
  26. ---------------->交换与排序  
  27. 将堆顶的元素与“无序区”中最后一个元素交换，“1,6,4,3,2,[10]”,其中[10]为有序区，[10]之前的为“无序区”  
  28. 此后，有序区，将不再参与“堆顶”元素的交换，为了便于理解，在下图中，我们暂且将“有序区”中的元素移除树  
  29. ++++++++++++++  
  30.           [1]  
  31.        |       |  
  32.      [6]      [4]  
  33.       |           
  34.    [3] [2]       
  35.   
  36. 接下来，和“初始堆”的过程一样：从树的底部往上，比较节点，最大元素放在“顶部”，并将其交换到“有序区”  
  37. ++++++++++++++  
  38.           [6]  
  39.        |       |  
  40.      [1]      [4]  
  41.       |           
  42.    [3] [2]  
  43. ++++++++++++++因为1调换位置后,[1][3][2]不满足大顶堆,递归  
  44.           [6]  
  45.        |       |  
  46.      [3]      [4]  
  47.       |           
  48.    [1] [2]  
  49. ++++++++++++++(6交换到有序区,即[6]和最底层叶子节点[2]交换)  
  50.           [2]  
  51.        |       |  
  52.      [1]      [4]  
  53.       |           
  54.    [3]   
  55. ++++++++++++++(继续调整堆顶,基于交换原则,[2]和[4]交换)  
  56.           [4]  
  57.        |      |   
  58.      [3]     [2]  
  59.       |           
  60.    [1]   
  61. ++++++++++++++(4交换到有序区,即[4]与最底层叶子节点[1]交换)       
  62.      [1]        
  63.       |           
  64.    [3] [2]  
  65. .....  
  66. 最终数组为:[1,2,3,4,6,10]  

 

Java代码  

  1. public class MaxHeapSort {  
  2.   
  3.     public static void sort(int[] sources,int length){  
  4.         //堆将会以"二叉树"的方式构建,在逻辑上,需要确保"左右"两边树高一致.  
  5.         int i = length/2;  
  6.         //首先构建一次"初始堆",从树的叶子节点"倒序"遍历所有的节点  
  7.         //此次的目的,就是将整棵树中,值最大的节点,交换到树的根部.  
  8.         int max = length - 1;//最大索引  
  9.         for(; i>=0; i--){  
  10.             heap(sources,i,max);  
  11.         }  
  12.         //"交换"位置,每循环一次,都会把当前树的"根"(也是最大值)和"当前无序区域"的最后一个位置交换  
  13.         //交换之后,最后一个位置是最大值,此位置之前的节点,为"无序区域".  
  14.         //每执行一次heap方法,都会将当前"无序区域"的最大值放在"根"部.  
  15.         //每交换一次,"无序区域"的长度-1(因为最大值已经产生,并交换到了当前"区域"的尾部,下一次heap,就不需要参与)  
  16.         for(i = max; i>= 1;i--){  
  17.             int tmp = sources[0];  
  18.             sources[0] = sources[i];  
  19.             sources[i] = tmp;  
  20.             max--;//将source[max]"移动"到有序区,将不再参与此后的heap过程  
  21.             heap(sources, 0, max);//从"堆顶"调整,每次只需比较最上层2个节点  
  22.         }  
  23.     }  
  24.       
  25.     /** 
  26.      *  
  27.      * @param sources 原始数组 
  28.      * @param i 当前节点位置 
  29.      * @param max (需要比较的范围,即剩余的无序数组的最大索引) 
  30.      */  
  31.     private static void heap(int[] sources,int i,int max){  
  32.         //计算出当前"节点i"的左右子节点的位置(在数组中的位置)  
  33.         int l = 2 * i + 1;//左  
  34.         int r = 2 * i + 2;//右  
  35.         int c = i;//当前索引  
  36.         //找出"当前节点""左右子节点"三个节点中,最大的值,以构建"大顶堆"  
  37.         if(l <= max && sources[l] > sources[c]){  
  38.             c = l;  
  39.         }  
  40.         if(r <= max && sources[r] > sources[c]){  
  41.             c = r;  
  42.         }  
  43.         if(c != i){  
  44.             //交换数据  
  45.             int tmp = sources[i];  
  46.             sources[i] = sources[c];  
  47.             sources[c] = tmp;  
  48.             heap(sources, c, max);//每次交换,重新调整,满足"大顶堆"要求  
  49.         }  
  50.     }  
  51.     /** 
  52.      * @param args 
  53.      */  
  54.     public static void main(String[] args) {  
  55.         int[] sources = {11,0,20,8,13,3,4,7};  
  56.         sort(sources,sources.length);  
  57.         System.out.println(Arrays.toString(sources));  
  58.   
  59.     }  
  60.   
  61. }  

 

五.选择排序/交换排序

特点:每次遍历"无序区域"时,找到一个最小的值,并和"无序区域"的第一个元素交换位置,至此"无序区域"的剩余元素,继续执行上述遍历过程..它和"冒泡排序"异曲同工.【从无序区中“选择”出最小的元素，交换到“无序区”的头部】

 

场景：算法不稳定，元素个数较小时，时间复杂度O(n^2),空间复杂度O(1)

 

Java代码  

  1. 原始数组：[4,3,10,6,2,1]  
  2. 过程：将数组分为“有序区”，“无序区”，每次遍历都从“无序区”找到最小的元素“交换”到“有序区”的最前面  
  3. ------------->[]4,3,10,6,2,1;初始时有序区为空（实现有所差异）  
  4. ---->[1],4,3,10,6,2   当前无序区中，1为最小，那么把1放在“无序区”的最前面，我们也可以认为1位于有序区的最后面  
  5. ---->[1,2],4,3,10,6    将2放在“无序区”的最前面，也可以认为为“有序区”的最后面  
  6. ---->[1,2,3]4,10,6  
  7. ---->[1,2,3,4],10,6  
  8. ---->[1,2,3,4,6],10  
  9. ....  

 

Java代码  

  1. public class SelectSort {  
  2.   
  3.     public static void sort(int[] sources){  
  4.         int length = sources.length;  
  5.         int n;  
  6.         for(int i=0; i < length -1; i++){  
  7.             n = i;  
  8.             for(int j= i+1; j< length; j++){  
  9.                 if(sources[j] < sources[i]){  
  10.                     n = j;  
  11.                 }  
  12.             }  
  13.             if(n != i){  
  14.                 int tmp = sources[i];  
  15.                 sources[i] = sources[n];  
  16.                 sources[n] = tmp;  
  17.             }  
  18.         }  
  19.     }  
  20.     /** 
  21.      * @param args 
  22.      */  
  23.     public static void main(String[] args) {  
  24.         int[] sources = {2,15,3,100,87,-1,34,25,77,80,62,11,7,2,55,22};  
  25.         sort(sources);  
  26.         System.out.println(Arrays.toString(sources));  
  27.     }  
  28. }  

 

六.插入排序:

特点:和冒泡排序很像,"有序区域"在数组的前部,依次遍历"无序区域"中的元素,并将"无序区域"中的第一个元素,和"有序区域"中的元素比较(从后往前),并将此元素不断向前"推进".它和“选择排序”也很相似。[依次将无序区中的元素“插入”到有序区中]

 

场景：算法稳定，元素格式较小时，时间复杂度O(n^2),空间复杂度O(1)

Java代码  

  1. 原始数组：[4,3,10,6,2,1]  
  2. 过程：和“选择排序”很像，只不过“无序区”中的元素是和“有序区”比较(选择排序，是从无序区中“选择”最小的，放入有序区)，然后一次在“有序区”中交换位置。  
  3. ------------->[4],3,10,6,2,1;初始时有序区为空也可以为第一个元素（实现有所差异）  
  4. ---->[3,4],10,6,2,1   首先将无序区中的3,和有序区中的4比较，并交换位置，此时3进入有序区  
  5. ---->[3,4,10],6,2,1   将10与[3,4]从后往前比较，并交换位置  
  6. ---->[3,4,6,10],2,1  
  7. ---->[2,3,4,6,10],1  
  8. ....  

 

Java代码  

  1. public class InsertSort {  
  2.   
  3.     public static void sort(int[] sources){  
  4.         int length = sources.length;  
  5.         int n;  
  6.         for(int i = 1; i < length; i++){  
  7.             n = i - 1;  
  8.             int cv = sources[i];//当前需要比较的元素  
  9.             //依次遍历此元素所在位置之前的元素集合(此集合为已排序的集合)  
  10.             while(n >=0 && cv < sources[n]){  
  11.                 //如果当前元素,比"已排序集合"的元素值小  
  12.                 //往前交换位置,类似于"冒泡"  
  13.                 sources[n+1] = sources[n];  
  14.                 sources[n] = cv;  
  15.                 n--;  
  16.             }  
  17.         }  
  18.     }  
  19.     /** 
  20.      * @param args 
  21.      */  
  22.     public static void main(String[] args) {  
  23.         int[] sources = {0,2,15,3,100,87,-1,34};  
  24.         sort(sources);  
  25.         System.out.println(Arrays.toString(sources));  
  26.   
  27.     }  
  28.   
  29. }  

 

七.希尔排序

特点："列排序"，将数组数据，在逻辑上分成“多个列”，然后每一列排序。每次遍历成功后，列数减半，继续排序，直到最后为一列时，进行一次插入排序。速度比“插入排序”要快，因为减少了元素交换的次数，是“插入排序”的改进版本。

 

场景：算法不稳定，元素个数较小时，时间复杂度O(n*logn),空间复杂度O(n^s),其中s为组数。

 

Java代码  

  1. 原始数组：[4,3,10,6,2,1，8,5]  
  2. 过程："列"排序，依次将数组，分为N个列(length/2)，然后对每一列进行排序。直到最后列数为1.(每次排序之后，列数减半)  
  3.   
  4. ------------>8个元素，分为4列  
  5. 4,3,10,6  
  6. 2,1,8,5  
  7. ----->对每一列进行排序(竖向)  
  8. 2,1,8,5  
  9. 4,3,10,6  
  10. 此时数组为[2,1,8,5,4,3,10,6]  
  11. ----->然后分为2列(4列变为2列，列数减半)  
  12. 2,1  
  13. 8,5  
  14. 4,3  
  15. 10,6  
  16. ----->排序  
  17. 2,1  
  18. 4,3  
  19. 8,5  
  20. 10,6  
  21. 此时数组为[2,1,4,3,8,5,10,6]  
  22. ------>然后为1列，直接对数组进行“插入排序”即可  

 

Java代码  

  1. public class ShellSort {  
  2.   
  3.       
  4.     /** 
  5.      * 我们可以简单的认为shell排序就是“列排序” 
  6.      * @param sources 
  7.      */  
  8.     public static void sort(int[] sources){  
  9.         int l = sources.length;  
  10.         int i = l;  
  11.         do{  
  12.             i = i/2;//列数，“在逻辑上”有多少列数据，  
  13.             insert(sources,i,l);  
  14.         }while(i > 1);  
  15.     }  
  16.       
  17.     private static void insert(int[] sources,int i,int length){  
  18.         int j;  
  19.         //i为当前的列数  
  20.         //lenght:为总数据两  
  21.         //j为当前排序时，在一列中所处的位置  
  22.         for(int t = i;t < length; t++){  
  23.             j = t - i;  
  24.             int cv = sources[t];  
  25.             while(j >=0 && cv < sources[j]){  
  26.                 sources[j + i] = sources[j];  
  27.                 sources[j] = cv;  
  28.                 j = j-i;  
  29.             }  
  30.         }  
  31.     }  
  32.     /** 
  33.      * @param args 
  34.      */  
  35.     public static void main(String[] args) {  
  36.         int[] sources = {2,15,3,100,87,3,-1,3,0};  
  37.         sort(sources);  
  38.         System.out.println(Arrays.toString(sources));  
  39.   
  40.     }  
  41. }  

原文链接：[http://wely.iteye.com/blog/2228812]

时间： 2024-10-03 15:28:23

java 排序算法的相关文章

java排序算法

Java 1.0和1.1库都缺少的一样东西是算术运算,甚至没有最简单的排序运算方法.因此,我们最好创建一个Vector,利用经典的Quicksort(快速排序)方法对其自身进行排序. 编写通用的排序代码时,面临的一个问题是必须根据对象的实际类型来执行比较运算,从而实现正确的排序.当然,一个办法是为每种不同的类型都写一个不同的排序方法.然而,应认识到假若这样做,以后增加新类型时便不易实现代码的重复利用. 程序设计一个主要的目标就是"将发生变化的东西同保持不变的东西分隔开".在这里,保持不

Java排序算法总结之插入排序_java

本文实例讲述了Java插入排序方法.分享给大家供大家参考.具体分析如下: 有一个已经有序的数据序列,要求在这个已经排好的数据序列中插入一个数,但要求插入后此数据序列仍然有序,这个时候就要用到插入排序法.本文主要介绍的是插入排序的java实现.   插入排序的基本操作就是将一个数据插入到已经排好序的有序数据中,从而得到一个新的.个数加一的有序数据.比较和交换的时间复杂度为O(n^2),算法自适应,对于数据已基本有序的情况,时间复杂度为O(n),算法稳定,开销很低.算法适合于数据已基本有序或者数据量

Java排序算法总结之希尔排序_java

本文实例讲述了Java排序算法总结之希尔排序.分享给大家供大家参考.具体分析如下: 前言:希尔排序(Shell Sort)是插入排序的一种.是针对直接插入排序算法的改进.该方法又称缩小增量排序,因DL．Shell于1959年提出而得名.本文主要介绍希尔排序用Java是怎样实现的. 希尔排序(缩小增量法) 属于插入类排序,是将整个无序列分割成若干小的子序列分别进行插入排序.希尔排序并不稳定,O(1)的额外空间,时间复杂度为O(N*(logN)^2).最坏的情况下的执行效率和在平均情况下的执行效率相

5种java排序算法汇总工具类_java

工具类简单明了地总结了java的快速排序,希尔排序,插入排序,堆排序,归并排序五种排序算法,代码中并没有对这几种排序算法的一个说明,关于思想部分希望在自行查阅相关说明,这里只是对这几种算法进行一个概括,以供大家使用. public class Sort { public static <AnyType extends Comparable<? super AnyType>> void insertionSort(AnyType[] a) { insertionSort(a, 0,

Java排序算法总结之冒泡排序_java

本文实例讲述了Java排序算法总结之冒泡排序.分享给大家供大家参考.具体分析如下: 前言:冒泡排序(BubbleSort)就是依次比较相邻的两个数,将小数放在前面,大数放在后面. 下面让我们一起    来看冒泡排序在Java中的算法实现. 冒泡排序是计算机的一种排序方法,它的时间复杂度为O(n^2),虽然不及堆排序.快速排序的O(nlogn,底数为2),但是有两个优点: 1."编程复杂度"很低,很容易写出代码: 2.具有稳定性,这里的稳定性是指原序列中相同元素的相对顺序仍然保持到排序后

Java排序算法&amp;amp;nbsp;堆排序

1991年计算机先驱奖获得者.斯坦福大学计算机科学系教授罗伯特·弗洛伊德(Robert W．Floyd)和威廉姆斯(J．Williams)在1964年共同发明了著名的堆排序算法( Heap Sort ).本文主要介绍堆排序用Java来实现. AD: 堆积排序(Heapsort)是指利用堆积树(堆)这种资料结构所设计的一种排序算法,可以利用数组的特点快速定位指定索引的元素.堆排序是不稳定的排序方法,辅助空间为O(1), 最坏时间复杂度为O(nlog2n) ,堆排序的堆序的平均性能较接近于最坏性能.

Java排序算法&amp;amp;nbsp;插入排序

有一个已经有序的数据序列,要求在这个已经排好的数据序列中插入一个数,但要求插入后此数据序列仍然有序,这个时候就要用到插入排序法.本文主要介绍的是插入排序的java实现. AD: 插入排序的基本操作就是将一个数据插入到已经排好序的有序数据中,从而得到一个新的.个数加一的有序数据.比较和交换的时间复杂度为O(n^2),算法自适应,对于数据已基本有序的情况,时间复杂度为O(n),算法稳定,开销很低.算法适合于数据已基本有序或者数据量小的情况. 插入算法把要排序的数组分成两部分:第一部分包含了这个数组的

十种JAVA排序算法实例_java

排序算法有很多,所以在特定情景中使用哪一种算法很重要.为了选择合适的算法,可以按照建议的顺序考虑以下标准: (1)执行时间 (2)存储空间 (3)编程工作  对于数据量较小的情形,(1)(2)差别不大,主要考虑(3):而对于数据量大的,(1)为首要.  一.冒泡(Bubble)排序 复制代码 代码如下: void BubbleSortArray() {       for(int i=1;i<n;i++)       {         for(int j=0;i<n-i;j++)      

Java排序算法&amp;amp;nbsp;归并排序

归并排序(Merge)是将两个(或两个以上)有序表合并成一个新的有序表,即把待排序序列分为若干个子序列,每个子序列是有序的.然后再把有序子序列合并为整体有序序列. 归并排序是建立在归并操作上的一种有效的排序算法.该算法是采用分治法(Divide and Conquer)的一个非常典型的应用. 将已有序的子序列合并,得到完全有序的序列:即先使每个子序列有序,再使子序列段间有序.若将两个有序表合并成一个有序表,称为2-路归并. 归并排序算法稳定,数组需要O(n)的额外空间,链表需要O(log(n))

Java排序算法 归并排序

归并排序(Merge)是将两个(或两个以上)有序表合并成一个新的有序表,即把待排序序列分为若干个子序列,每个子序列是有序的.然后再把有序子序列合并为整体有序序列. 归并排序是建立在归并操作上的一种有效的排序算法.该算法是采用分治法(Divide and Conquer)的一个非常典型的应用.将已有序的子序列合并,得到完全有序的序列:即先使每个子序列有序,再使子序列段间有序.若将两个有序表合并成一个有序表,称为2-路归并. 归并排序算法稳定,数组需要O(n)的额外空间,链表需要O(log(n))的