java 相关排序

对排序算法性能影响有：

1、数据比较的次数（处理时间上影响）

2、数据移动的次数（处理时间上影响）

3、内存空间占用的大小

在日常开发中使用排序，就要考虑以上情况

排序（Sort）是指将数据元素按照指定关键字值的大小递增（或递减）次序重新排列。

1、插入排序

1.1、直接插入排序

基本思想：在要排序的一组数中，假设前面(n-1)[n>=2] 个数已经是排好顺序的，现在要把第n个数插到前面的有序数中，使得这n个数也是排好顺序的。如此反复循环，直到

全部排好顺序直接插入排序流程

公用的工具类

public class ArrayPrintUtils { public static void print(int[] keys){ int length = keys.length; for(int i=0; i<length; i++){ System.out.print(keys[i] + " "); } System.out.println(); } }

直接插入排序

public class InsertSort { public static void main(String[] args) { int[] keys = {32,26,87,72,26,17}; insertSort(keys); } public static void insertSort(int[] keys){ System.out.println("直接插入排序（升序）"); int length = keys.length; for(int i=1; i<length; i++){ int temp = keys[i]; int j = 0; /** * 开始： * j=i-1位置开始，比如 i=1,j=0; * i=2,j=1; * i=3,j=2 * 满足条件： * j>=0 和 temp<keys[j] * * 需注意：在集合中 是和该元素前面的元素做比较 */ int k=0; for(j=i-1; j>=0 && temp<keys[j]; j--){ //升序 // for(j=i-1; j>=0 && temp>keys[j]; j--){//降序 /** * 满足的条件：后面的数比前面的数小 * 交换位置 */ keys[j+1] = keys[j]; k++; } System.out.println("第"+i+"趟 比较次数k="+k); keys[j+1] = temp; System.out.println("第"+i+"趟 temp="+temp); ArrayPrintUtils.print(keys); System.out.println(); } } }

1.2、希尔排序 基本思想：算法先将要排序的一组数按某个增量d（n/2,n为要排序数的个数）分成若干组，每组中记录的下标相差d.对每组中全部元素进行直接插入排序，然后再用一个较小的增量（d/2）对它进行分组，在每组中再进行直接插入排序。当增量减到1时，进行直接插入排序后，排序完成。

希尔排序流程

希尔排序代码

public class ShellSort { public static void main(String[] args) { int[] keys = {38,55,65,97,27,76,27,13,19}; shellSort(keys); } public static void shellSort(int[] keys){ System.out.println("希尔排序（升序）"); int length = keys.length; for(int delta=length/2; delta>0; delta/=2){ //控制增量每趟减半 for(int i=delta; i<length; i++){ int temp = keys[i]; int j= 0; // for(j=i-delta; j>=0 && temp<keys[j]; j-=delta){ //升序 for(j=i-delta; j>=0 && temp>keys[j]; j-=delta){ //降序 keys[j+delta] = keys[j]; // System.out.println("keys["+(j+delta)+"] = " + keys[j]); } keys[j+delta] = temp; } System.out.println("分组delta="+delta); ArrayPrintUtils.print(keys); System.out.println(); } } }

2、交换排序 2.1、冒泡排序 基本思想：在要排序的一组数中，对当前还未排好序范围内的全部数自上而下对相邻的两个数依次进行比较和调整，让较大的数往下沉，较小的往上冒。既每当相邻的数比较后发现它们的排序与排序要求相反时，它们就互换位置。

冒泡排序流程

冒泡排序代码

public class BubbleSort { public static void main(String[] args) { int[] keys = {1,2,3,4,5,6,7,8}; // bubbleSort(keys, true); //升序 bubbleSort(keys, false); //降序 } public static void bubbleSort(int[] keys, boolean asc) //冒泡排序，asc取值true（升序）、false（降序） { System.out.println("冒泡排序（"+(asc?"升":"降")+"序）"); boolean exchange=true; //是否交换的标记 int length = keys.length; for (int i=1; i<length && exchange; i++) //有交换时再进行下一趟，最多n-1趟 { exchange=false; //假定元素未交换 for (int j=0; j<length-i; j++){ //一趟比较、交换 if (asc ? keys[j]>keys[j+1] : keys[j]<keys[j+1])//相邻元素比较，若反序，则交换 { swap(keys, j, j+1); exchange=true; //有交换 } } System.out.print("第"+i+"趟，下标0～"+(length-i)+"，"); ArrayPrintUtils.print(keys); } } private static void swap(int[] keys, int i, int j) //交换keys[i]与keys[j]元素，i、j范围由调用者控制 { int temp = keys[j]; keys[j] = keys[i]; keys[i] = temp; } } 2.2、快速排序（是对冒泡排序的一种改进） 基本思想：选择一个基准元素,通常选择第一个元素或者最后一个元素,通过一趟扫描，将待排序列分成两部分,一部分比基准元素小,一部分大于等于基准元素,此时基准元素在其排好序后的正确位置,然后再用同样的方法递归地排序划分的两部分。

快速排序流程

快速排序代码

public class QuickSort { public static void main(String[] args) { int[] keys = {38,38,97,75,61,19,26,49}; quickSort(keys); } public static void quickSort(int[] keys) //快速排序（升序） { System.out.println("快速排序（升序）"); quickSort(keys, 0, keys.length-1); } /** * 对存于keys数组begin～end之间的子序列进行一趟快速排序，递归算法 * @param keys * @param begin 开始的下标值 * @param end 结束的下标值 */ private static void quickSort(int[] keys, int begin, int end) { int length = keys.length; if (begin>=0 && begin<length && end>=0 && end<length && begin<end)//序列有效 { int i=begin, j=end; //i、j下标分别从子序列的前后两端开始 int vot=keys[i]; //子序列第一个值作为基准值 while (i!=j) //每趟来回比较2次 { //第一趟 基准值 在前面 和 从后向前 来作比较 while (i<j && keys[j]>=vot){ //（升序）从后向前寻找较小值，不移动与基准值相等元素 // while (i<j && vot>=keys[j]){ //（降序）从后向前寻找较大值，不移动与基准值相等元素 j--; } System.out.println("j = "+j); if (i<j){ keys[i++]=keys[j]; //子序列后端较小元素向前移动 } //第二趟 基准值 在后面 和 从前向后 来作比较 while (i<j && keys[i]<=vot){ //（升序）从前向后寻找较大值，不移动与基准值相等元素 // while (i<j && keys[i]>=vot){ //（降序）从前向后寻找较小值，不移动与基准值相等元素 i++; } if (i<j){ keys[j--]=keys[i]; //子序列前端较大元素向后移动 } System.out.println("j = "+ j); } keys[i]=vot; //基准值到达最终位置 System.out.print("下标"+begin+"～"+end+"， vot="+vot+"， "); ArrayPrintUtils.print(keys); quickSort(keys, begin, j-1); //前端子序列再排序，递归调用 quickSort(keys, i+1, end); //后端子序列再排序，递归调用 } } }

3、选择排序 3.1、简单(直接)选择排序 基本思想：第一趟从n个元素的数据序列中选出关键字最小（或最大）的元素放到最前（或最后）位置，下一趟再从n-1个元素中选出最小（大）的元素并放到次前（后）位置，以此类推，经过n-1趟完成排序。 直接选择排序流程

直接选择排序代码

public class SimpleSort { public static void main(String[] args) { int[] keys = {38,97,26,19,38,15}; selectSort(keys); } public static void selectSort(int[] keys) //直接选择排序（升序） { System.out.println("直接选择排序（升序）"); int length = keys.length; for (int i=0; i<length-1; i++) //n-1趟排序 { int min=i; for (int j=i+1; j<length; j++){ //每趟在从keys[i]开始的子序列中寻找最小元素 if (keys[j]<keys[min]){ //（升序） // if (keys[j]>keys[min]){ //（降序） min = j; //min记住本趟最小元素下标 } } System.out.print("第"+(i+1)+"趟，下标"+i+"～"+(length-1)+"，最小的下标值="+min+"， "); if (min!=i) //将本趟最小元素交换到前边 swap(keys, i, min); ArrayPrintUtils.print(keys); } } private static void swap(int[] keys, int i, int j) //交换keys[i]与keys[j]元素，i、j范围由调用者控制 { int temp = keys[j]; keys[j] = keys[i]; keys[i] = temp; } }

3.2、堆排序 基本思想：堆排序是一种树形排序，是对直接选择排序的有效改进版

堆的定义如下：具有n个元素的序列（h1,h2,…,hn),当且仅当满足（hi>=h2i,hi>=2i+1）或（hi<=h2i,hi<=2i+1） (i=1,2,…,n/2)时称之为堆。在这里只讨论满足前者条件的堆。由堆的定义可以看出，堆顶元素（即第一个元素）必为最大项（大顶堆）。完全二叉树可以很直观地表示堆的结构。堆顶为根，其它为左子树、右子树。初始时把要排序的数的序列看作是一棵顺序存储的二叉树，调整它们的存储序，使之成为一个堆，这时堆的根节点的数最大。然后将根节点与堆的最后一个节点交换。然后对前面(n-1)个数重新调整使之成为堆。依此类推，直到只有两个节点的堆，并对它们作交换，最后得到有n个节点的有序序列。从算法描述来看，堆排序需要两个过程，一是建立堆，二是堆顶与堆的最后一个元素交换位置。所以堆排序有两个函数组成。一是建堆的渗透函数，二是反复调用渗透函数实现排序的函数

堆排序流程

4、归并排序 基本排序：归并排序法是将两个（或两个以上）有序表合并成一个新的有序表，即把待排序序列分为若干个子序列，每个子序列是有序的。然后再把有序子序列 合并为整体有序序列。 归并排序流程

归并排序代码

public class MergeSort { public static void main(String[] args) { int[] keys = {97,82,75,53,17,61,70,12,61,58,26}; mergeSort(keys); } public static void mergeSort(int[] X) //归并排序（升序） { System.out.println("归并排序（升序）"); int length = X.length; System.out.print("原序列长度n=" + length+" "); ArrayPrintUtils.print(X); int[] Y = new int[length]; //Y数组长度同X数组 int n=1; //排序子序列长度，初值为1 while (n<length) { mergepass(X, Y, n); //一趟归并，将X中若干相邻子序列归并到Y n*=2; //子序列长度加倍 if (n<length) { mergepass(Y, X, n); //一趟归并，将Y中若干相邻子序列再归并到X n*=2; } } } //一趟归并，将X中若干相邻子序列两两归并到Y中，子序列长度为n private static void mergepass(int[] X, int[] Y, int n) { System.out.print("子序列长度n="+n+" "); for (int i=0; i<X.length; i+=2*n){ //将X中若干相邻子序列归并到Y中 merge(X, Y, i, i+n, n); //一次归并 } ArrayPrintUtils.print(Y); } //一次归并（升序） //将X中分别以begin1、begin2开始的两个相邻子序列归并（升序）到Y中，子序列长度为n private static void merge(int[] X, int[] Y, int begin1, int begin2, int n) { int i=begin1, j=begin2, k=begin1; while (i<begin1+n && j<begin2+n && j<X.length){ //将X中两个相邻子序列归并到Y中 if (X[i]<X[j]){ //（升序）将较小值复制到Y中 // if (X[i]>X[j]) //（降序）将较大值复制到Y中 Y[k++]=X[i++]; }else{ Y[k++]=X[j++]; } } while (i<begin1+n && i<X.length){ //将前一个子序列剩余元素复制到Y中，子序列长度可能不足n Y[k++]=X[i++]; } while (j<begin2+n && j<X.length){ //将后一个子序列剩余元素复制到Y中 Y[k++]=X[j++]; } } }

5、基数排序 基本思想：将所有待比较数值（正整数）统一为同样的数位长度，数位较短的数前面补零。然后从最低位开始，依次进行一次排序。这样从最低位排序一直到最 高位排序完成以后，数列就变成一个有序序列。

基数排序流程

基数排序代码

public class RadixSort { public static void main(String[] args) { int keys[] = { 135, 242, 192, 93, 345, 11, 24, 19 }; sort(keys); } public static void sort(int[] array) { // 首先确定排序的趟数; int max = array[0]; for (int i = 1; i < array.length; i++) { if (array[i] > max) { max = array[i]; } } int time = 0; // 判断位数; while (max > 0) { max /= 10; time++; } // 建立10个队列; List<ArrayList> queue = new ArrayList<ArrayList>(); for (int i = 0; i < 10; i++) { ArrayList<Integer> queue1 = new ArrayList<Integer>(); queue.add(queue1); } // 进行time次分配和收集; for (int i = 0; i < time; i++) { // 分配数组元素; for (int j = 0; j < array.length; j++) { // 得到数字的第time+1位数【精确到小数点后一位】 int x = array[j] % (int) Math.pow(10, i + 1) / (int) Math.pow(10, i); ArrayList<Integer> queue2 = queue.get(x); //返回此列表中指定位置上的元素 queue2.add(array[j]); //将指定的元素插入此列表中的指定位置 queue.set(x, queue2); //用指定的元素替代此列表中指定位置上的元素 } System.out.println(queue.toString() ); int count = 0;// 元素计数器; // 收集队列元素; for (int k = 0; k < 10; k++) { while (queue.get(k).size() > 0) { ArrayList<Integer> queue3 = queue.get(k); //内存地址一样的 array[count] = queue3.get(0); queue3.remove(0); //移除此列表中指定位置上的元素 count++; } } } ArrayPrintUtils.print(array); } }

使用的场景