Java常用几种排序详解

8 种排序之间的关系 1 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 2 3 34 15 35 25 53 51 6 int temp 0 7 for int i 1 i 0j 11 a j 1 a j 将大于 temp 的值整体后移一个单位 12 13 a j 1 temp 14 15 for int i 0 i a length i 16 System out println a i 17 18 2 2 希尔排序 最小增量排序 希尔排序 最小增量排序 1 基本思想 算法先将要排序的一组数按某个增量 d n 2 n 为要排序数的个数 分成若干组 每组中 记录的下标相差 d 对每组中全部元素进行直接插入排序 然后再用一个较小的增量 d 2 对它进行分组 在每组中再进行直接插入排序 当增量减到 1 时 进行直接插入排序后 排序完成 2 实例 3 3 用 用 javajava 实现实现 1 public class shellSort 2 public shellSort 3 int a 1 54 6 3 78 34 12 45 56 100 4 double d1 a length 5 int temp 0 6 while true 7 d1 Math ceil d1 2 8 int d int d1 9 for int x 0 x d x 10 for int i x d i 0j d 14 a j d a j 15 16 a j d temp 17 18 19 if d 1 20 break 21 22 for int i 0 i a length i 23 System out println a i 24 25 3 3 简单选择排序简单选择排序 1 基本思想 在要排序的一组数中 选出最小的一个数与第一个位置的数交换 然后在剩下的数当中再找最小的与第二个位置的数交换 如此循环到倒数第二个数和最后一个数比较为止 2 实例 3 用 java 实现 1 public class selectSort 2 public selectSort 3 int a 1 54 6 3 78 34 12 45 4 int position 0 5 for int i 0 i a length i 6 7 int j i 1 8 position i 9 int temp a i 10 for j a length j 11 if a j temp 12 temp a j 13 position j 14 15 16 a position a i 17 a i temp 18 19 for int i 0 i 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 实现 1 import java util Arrays 2 3 public class HeapSort 4 int a 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 5 public HeapSort 6 heapSort a 7 8 public void heapSort int a 9 System out println 开始排序 10 int arrayLength a length 11 循环建堆 12 for int i 0 i 0 i 33 k 保存正在判断的节点 34 int k i 35 如果当前 k 节点的子节点存在 36 while k 2 1 lastIndex 37 k 节点的左子节点的索引 38 int biggerIndex 2 k 1 39 如果 biggerIndex 小于 lastIndex 即 biggerIndex 1 代表的 k 节点的右子节点存在 40 if biggerIndex lastIndex 41 若果右子节点的值较大 42 if data biggerIndex data biggerIndex 1 43 biggerIndex 总是记录较大子节点的索引 44 biggerIndex 45 46 47 如果 k 节点的值小于其较大的子节点的值 48 if data k data biggerIndex 49 交换他们 50 swap data k biggerIndex 51 将 biggerIndex 赋予 k 开始 while 循环的下一次循环 重新保 证 k 节点的值大于其左右子节点的值 52 k biggerIndex 53 else 54 break 55 56 5 5 冒泡排序冒泡排序 1 基本思想 在要排序的一组数中 对当前还未排好序的范围内的全部数 自上而下对相邻的两个数 依次进行比较和调整 让较大的数往下沉 较小的往上冒 即 每当两相邻的数比较后发现它们的排序与 排序要求相反时 就将它们互换 2 实例 3 用 java 实现 1 public class bubbleSort 2 public bubbleSort 3 int a 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 4 int temp 0 5 for int i 0 i a length 1 i 6 for int j 0 ja j 1 8 temp a j 9 a j a j 1 10 a j 1 temp 11 12 13 14 for int i 0 i a length i 15 System out println a i 16 17 18 6 6 快速排序快速排序 1 基本思想 选择一个基准元素 通常选择第一个元素或者最后一个元素 通过一趟扫描 将待排序列 分成两部分 一部分比基准元素小 一部分大于等于基准元素 此时基准元素在其排好序后的正确位置 然后 再用同样的方法递归地排序划分的两部分 2 实例 3 用 java 实现 1 public class quickSort 2 int a 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 3 public quickSort 4 quick a 5 for int i 0 i a length i 6 System out println a i 7 8 public int getMiddle int list int low int high 9 int tmp list low 数组的第一个作为中轴 10 while low high 11 while low tmp 12 13 high 14 15 list low list high 比中轴小的记录移到低端 16 while low high 18 19 list high list low 比中轴大的记录移到高端 20 21 list low tmp 中轴记录到尾 22 return low 返回中轴的位置 23 24 public void quickSort int list int low int high 25 if low 0 查看数组是否为空 33 quickSort a2 0 a2 length 1 34 35 36 7 7 归并排序 归并排序 1 基本排序 归并 Merge 排序法是将两个 或两个以上 有序表合并成一个新的有序表 即把待排 序序列分为若干个子序列 每个子序列是有序的 然后再把有序子序列合并为整体有序序列 2 实例 3 3 用 用 javajava 实现实现 1 import java util Arrays 2 3 public class mergingSort 4 int a 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 5 public mergingSort 6 sort a 0 a length 1 7 for int i 0 i a length i 8 System out println a i 9 10 public void sort int data int left int right 11 TODO Auto generated method stub 12 if left right 13 找出中间索引 14 int center left right 2 15 对左边数组进行递归 16 sort data left center 17 对右边数组进行递归 18 sort data center 1 right 19 合并 20 merge data left center right 21 22 23 24 public void merge int data int left int center int right 25 TODO Auto generated method stub 26 int tmpArr new int data length 27 int mid center 1 28 third 记录中间数组的索引 29 int third left 30 int tmp left 31 while left center 36 else 37 tmpArr third data mid 38 39 40 剩余部分依次放入中间数组 41 while mid right 42 tmpArr third data mid 43 44 while left center 45 tmpArr third data left 46 47 将中间数组中的内容复制回原数组 48 while tmp right 49 data tmp tmpArr tmp 50 51 System out println Arrays toString data 52 53 54 8 8 基数排序 基数排序 1 基本思想 将所有待比较数值 正整数 统一为同样的数位长度 数位较短的数前面补零 然后 从最低位开始 依次进行一次排序 这样从最低位排序一直到最高位排序完成以后 数列就变成一个有序 序列 2 实例 3 用 java 实现 1 import java util ArrayList 2 import java util List 3 4 public class radixSort 5 int 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 6 public radixSort 7 sort a 8 for int i 0 i a length i 9 System out println a i 10 11 public void sort int array 12 13 首先确定排序的趟数 14 int max array 0 15 for int i 1 imax 17 max array i 18 19 20 21 int time 0 22 判断位数 23 while max 0 24 max 10 25 time 26 27 28 建立 10 个队列 29 List queue new ArrayList 30 for int i 0 i 10 i 31 ArrayList queue1 new ArrayList 32 queue add queue1 33 34 35 进行 time 次分配和收集 36 for int i 0 i time i 37 38 分配数组元素 39 for int j 0 j array length j 40 得到数字的第 time