【转载】java 排序算法

一.冒泡排序

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

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

 

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

 

原始数组：[4,3,10,6,2]   过程：每一次遍历，都会将“无序区”中最大的元素交换到数组的末尾   ------------    -- 3,4,10,6,2   -- 3,4,10,6,2   -- 3,4,6,10,2   -- 3,4,6,2,[10]   ------------    -- 3,4,6,2,[10]   -- 3,4,6,2,[10]   -- 3,4,2,[6,10]   ------------    -- 3,4,2,[6,10]   -- 3,2,[4,6,10]   ------------    -- 2,[3,4,6,10]   ----    结束：[2,3,4,6,10]  

二.快速排序

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

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

 

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

原始数组：[4,3,10,6,2]   过程：每次递归内的排序，总是先选择“标杆”,我们取递归区间的第一个元素为标杆   ------------    --- 标杆为4,右边开始交换,将比4小的交换   --- 2,3,10,6,[4]   --- 标杆为4,左边开始交换，将比4大的交换   --- 2,3,[4],6,10   ------------    ---- [4]的左右两边分别递归，分成2部分   (递归1),标杆为2   ---- 2,[3]   (递归2),标杆为6   ---- [6],10   ....   结束：[2,3,4,6,10]  
    public static void sort(int[] sources,int low,int high){           if(low   high){               int key = sources[low];//此轮比较的key,左边比key大,右边比key小.               int l = low;               int h = high;               int tmp;               while(l   h){                   //因为我们不能创建额外的数组,所以才取了"交换"数据的方式.                   //从右边开始,将比key大的交换到过来.                   while(l   h   sources[h]  = key){                       h--;                   }                   //右边找到了比key大的.                   if(l   h){                       //交换顺序                       tmp = sources[l];                       sources[l] = sources[h];                       sources[h] = tmp;                   }                   //从左边开始,将比key小的交换过来                   while(l   h   sources[l]  = key){                       l++;                   }                   if(l   h){                       tmp = sources[l];                       sources[l] = sources[h];                       sources[h] = tmp;                   }               }               sort(sources, low, l-1);               sort(sources, l+1, high);           }       }       /**       * @param args       */       public static void main(String[] args) {           int[] sources = {2,15,3,100,87,-1,34,25,77,80,62,11,7,2,55,22};           sort(sources, 0, sources.length -1);           System.out.println(Arrays.toString(sources));       }  

三.归并排序

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

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

 

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

    public static void sort(int[] sources,int begin,int end){           if(begin   end){               int range = end - begin;               int mid = begin + range/2;               sort(sources,begin,mid);//左段               sort(sources,mid + 1,end);//右端               merge(sources, begin, mid, end);           }       }              /**       * 对begin~mid,mid+1 ~end两段区间中的数据进行排序并合并       * @param sources       * @param begin       * @param mid       * @param end       */       private static void merge(int[] sources,int begin,int mid,int end){           int[] tmp = new int[end - begin + 1];           int b1 = begin;           int e1 = mid;           int b2 = mid+1;           int e2 = end;           int i=0;           for(;b1  = e1   b2  = e2 ; i++){               //填充tmp数组,并依此在两段数据区域中找到最小的               if(sources[b1]  = sources[b2]){                   tmp[i] = sources[b1];                   b1++;               }else{                   tmp[i] = sources[b2];                   b2++;               }           }           //到此为止,两段数据区域,已经至少一个被扫描完毕           if(b1   e1){               //如果b1~e1扫描完毕,那么可能b2~e2还有剩余               for(int t = b2;t   e2 + 1; t++){                   tmp[i] = sources[t];                   i++;               }           }           if(b2   e2){               //如果b2~e2扫描完毕,那么可能b1~e1还有剩余               for(int t = b1;t   e1 + 1; t++){                   tmp[i] = sources[t];                   i++;               }           }           //replace and fill:将tmp数组的数据,替换到source中,begin~end           //因为此时tmp中的数据是排序好的           i=0;           for(int t= begin;t  = end; t++){               sources[t] = tmp[i];               i++;           }           tmp = null;//       }              /**       * @param args       */       public static void main(String[] args) {           int[] sources = {1,0,20,8,13,3,4,7,-1};           sort(sources,0,sources.length -1 );           System.out.println(Arrays.toString(sources));       }  

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

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

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

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

 

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

原始数组：[4,3,10,6,2,1]   过程：首先构建一次“初始堆”，然后基于“初始堆”进行“交换”   ------------- 按照元素顺序，构建成树             [4]          |       |        [3]      [10]         |         |      [6] [2]     [1]   -------------- 初始堆，从树的叶子节点开始向上进行，最终需要将最大的元素，交换到“顶”部   -------------- 每个节点都和其左右子节点进行比较，将最大的元素，和当前节点交换,如果交换过程中,有打破"大顶堆"原则,将递归.   ++++++++++++++             [4]          |       |        [6]      [10]         |         |      [3] [2]     [1]   因为[6],[3],[2]中，6最大，因此6需要和3交换位置。至此，[3],[10]两个节点已经肃清   ++++++++++++++             [10]          |       |        [6]      [4]         |         |      [3] [2]     [1]   因为在[4],[6],[10]中，10最大，因此4需要和10交换位置；此过程依次进行，直到根节点。   到此为止数组为[10,6,4,3,2,1],全部为“无序区”   ---------------- 交换与排序   将堆顶的元素与“无序区”中最后一个元素交换，“1,6,4,3,2,[10]”,其中[10]为有序区，[10]之前的为“无序区”   此后，有序区，将不再参与“堆顶”元素的交换，为了便于理解，在下图中，我们暂且将“有序区”中的元素移除树   ++++++++++++++             [1]          |       |        [6]      [4]         |               [3] [2]        接下来，和“初始堆”的过程一样：从树的底部往上，比较节点，最大元素放在“顶部”，并将其交换到“有序区”   ++++++++++++++             [6]          |       |        [1]      [4]         |               [3] [2]   ++++++++++++++因为1调换位置后,[1][3][2]不满足大顶堆,递归             [6]          |       |        [3]      [4]         |               [1] [2]   ++++++++++++++(6交换到有序区,即[6]和最底层叶子节点[2]交换)             [2]          |       |        [1]      [4]         |               [3]    ++++++++++++++(继续调整堆顶,基于交换原则,[2]和[4]交换)             [4]          |      |         [3]     [2]         |               [1]    ++++++++++++++(4交换到有序区,即[4]与最底层叶子节点[1]交换)             [1]               |               [3] [2]   .....   最终数组为:[1,2,3,4,6,10]  
    public static void sort(int[] sources,int length){           //堆将会以"二叉树"的方式构建,在逻辑上,需要确保"左右"两边树高一致.           int i = length/2;           //首先构建一次"初始堆",从树的叶子节点"倒序"遍历所有的节点           //此次的目的,就是将整棵树中,值最大的节点,交换到树的根部.           int max = length - 1;//最大索引           for(; i =0; i--){               heap(sources,i,max);           }           //"交换"位置,每循环一次,都会把当前树的"根"(也是最大值)和"当前无序区域"的最后一个位置交换           //交换之后,最后一个位置是最大值,此位置之前的节点,为"无序区域".           //每执行一次heap方法,都会将当前"无序区域"的最大值放在"根"部.           //每交换一次,"无序区域"的长度-1(因为最大值已经产生,并交换到了当前"区域"的尾部,下一次heap,就不需要参与)           for(i = max; i = 1;i--){               int tmp = sources[0];               sources[0] = sources[i];               sources[i] = tmp;               max--;//将source[max]"移动"到有序区,将不再参与此后的heap过程               heap(sources, 0, max);//从"堆顶"调整,每次只需比较最上层2个节点           }       }              /**       *        * @param sources 原始数组       * @param i 当前节点位置       * @param max (需要比较的范围,即剩余的无序数组的最大索引)       */       private static void heap(int[] sources,int i,int max){           //计算出当前"节点i"的左右子节点的位置(在数组中的位置)           int l = 2 * i + 1;//左           int r = 2 * i + 2;//右           int c = i;//当前索引           //找出"当前节点""左右子节点"三个节点中,最大的值,以构建"大顶堆"           if(l  = max   sources[l]   sources[c]){               c = l;           }           if(r  = max   sources[r]   sources[c]){               c = r;           }           if(c != i){               //交换数据               int tmp = sources[i];               sources[i] = sources[c];               sources[c] = tmp;               heap(sources, c, max);//每次交换,重新调整,满足"大顶堆"要求           }       }       /**       * @param args       */       public static void main(String[] args) {           int[] sources = {11,0,20,8,13,3,4,7};           sort(sources,sources.length);           System.out.println(Arrays.toString(sources));       }  

五.选择排序/交换排序

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

 

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

 

原始数组：[4,3,10,6,2,1]   过程：将数组分为“有序区”，“无序区”，每次遍历都从“无序区”找到最小的元素“交换”到“有序区”的最前面   ------------- []4,3,10,6,2,1;初始时有序区为空（实现有所差异）   ---- [1],4,3,10,6,2   当前无序区中，1为最小，那么把1放在“无序区”的最前面，我们也可以认为1位于有序区的最后面   ---- [1,2],4,3,10,6    将2放在“无序区”的最前面，也可以认为为“有序区”的最后面   ---- [1,2,3]4,10,6   ---- [1,2,3,4],10,6   ---- [1,2,3,4,6],10   ....  
            for(int j= i+1; j  length; j++){                   if(sources[j]   sources[i]){                       n = j;                   }               }               if(n != i){                   int tmp = sources[i];                   sources[i] = sources[n];                   sources[n] = tmp;               }           }       }       /**       * @param args       */       public static void main(String[] args) {           int[] sources = {2,15,3,100,87,-1,34,25,77,80,62,11,7,2,55,22};           sort(sources);           System.out.println(Arrays.toString(sources));       }  

六.插入排序:

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

 

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

原始数组：[4,3,10,6,2,1]   过程：和“选择排序”很像，只不过“无序区”中的元素是和“有序区”比较(选择排序，是从无序区中“选择”最小的，放入有序区)，然后一次在“有序区”中交换位置。   ------------- [4],3,10,6,2,1;初始时有序区为空也可以为第一个元素（实现有所差异）   ---- [3,4],10,6,2,1   首先将无序区中的3,和有序区中的4比较，并交换位置，此时3进入有序区   ---- [3,4,10],6,2,1   将10与[3,4]从后往前比较，并交换位置   ---- [3,4,6,10],2,1   ---- [2,3,4,6,10],1   ....  
            int cv = sources[i];//当前需要比较的元素               //依次遍历此元素所在位置之前的元素集合(此集合为已排序的集合)               while(n  =0   cv   sources[n]){                   //如果当前元素,比"已排序集合"的元素值小                   //往前交换位置,类似于"冒泡"                   sources[n+1] = sources[n];                   sources[n] = cv;                   n--;               }           }       }       /**       * @param args       */       public static void main(String[] args) {           int[] sources = {0,2,15,3,100,87,-1,34};           sort(sources);           System.out.println(Arrays.toString(sources));       }  

七.希尔排序

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

 

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

 

原始数组：[4,3,10,6,2,1，8,5]   过程："列"排序，依次将数组，分为N个列(length/2)，然后对每一列进行排序。直到最后列数为1.(每次排序之后，列数减半)   ------------ 8个元素，分为4列   4,3,10,6   2,1,8,5   ----- 对每一列进行排序(竖向)   2,1,8,5   4,3,10,6   此时数组为[2,1,8,5,4,3,10,6]   ----- 然后分为2列(4列变为2列，列数减半)   2,1   8,5   4,3   10,6   ----- 排序   2,1   4,3   8,5   10,6   此时数组为[2,1,4,3,8,5,10,6]   ------ 然后为1列，直接对数组进行“插入排序”即可  
            i = i/2;//列数，“在逻辑上”有多少列数据，               insert(sources,i,l);           }while(i   1);       }              private static void insert(int[] sources,int i,int length){           int j;           //i为当前的列数           //lenght:为总数据两           //j为当前排序时，在一列中所处的位置           for(int t = i;t   length; t++){               j = t - i;               int cv = sources[t];               while(j  =0   cv   sources[j]){                   sources[j + i] = sources[j];                   sources[j] = cv;                   j = j-i;               }           }       }       /**       * @param args       */       public static void main(String[] args) {           int[] sources = {2,15,3,100,87,3,-1,3,0};           sort(sources);           System.out.println(Arrays.toString(sources));       }  
八种排序算法与代码实现（Java代码实现） 八大排序算法是：1、直接插入排序；2、希尔排序；3、简单选择排序；4、堆排序；5、冒泡排序；6、快速排序；7、归并排序；8、桶排序/基数排序。
十大排序算法(java实现万字详解) 什么是排序的稳定性? 稳定性：假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持 不变，即在原序列中，r[i]=r[j]，且r[i]在r[j]之前，而在排序后的序列中，r[i]仍在r[j]之前，则称这种排序算法是稳 定的；否则称为不稳定的。