`
ly_ltw
  • 浏览: 9372 次
文章分类
社区版块
存档分类
最新评论

java各种排序

 
阅读更多

Java各种排序

博客分类: 
 

Java排序分类为:

 

 * 1.插入排序(直接插入排序、折半插入排序、希尔排序); 

 * 2.交换排序(冒泡排序、快速排序); 

 * 3.选择排序(直接选择排序、堆排序); 

 * 4.归并排序; 

 * 5.基数排序。

 

下面实现代码为:

 

 

Java代码  收藏代码
  1. /* 
  2.  * To change this template, choose Tools | Templates 
  3.  * and open the template in the editor. 
  4.  */  
  5. package com.xiva.baseKnowledge;  
  6.   
  7. import java.util.Arrays;  
  8. import java.util.LinkedList;  
  9. import java.util.List;  
  10.   
  11.   
  12. /** 
  13.  * 1.插入排序(直接插入排序、折半插入排序、希尔排序);  
  14.  * 2.交换排序(冒泡排序、快速排序);  
  15.  * 3.选择排序(直接选择排序、堆排序);  
  16.  * 4.归并排序;  
  17.  * 5.基数排序。  
  18.  * @author XIVA 
  19.  */  
  20. public class SortPractice <T extends Comparable> {  
  21.       
  22.     /** 
  23.      * 直接插入排序 
  24.      * @Description 在要排序的一组数中,假设前面(n-1) [n>=2] 个数已经是排 
  25.             好顺序的,现在要把第n个数插到前面的有序数中,使得这n个数 
  26.             也是排好顺序的。如此反复循环,直到全部排好顺序 
  27.      * @param  array needing to sort 
  28.      * @param  direction of sorting, 0 represent desc, 1 represent asc, others don't sorting. 
  29.      */  
  30.     public void directInsertSort(T[] array, int direction){  
  31.           
  32.         //升序  
  33.         if( direction == 1){  
  34.             for(int i=0; i< array.length; i++){  
  35.                 for(int j=0; j< i; j ++){  
  36.                     if( array[i].compareTo(array[j]) < 0 ){  
  37.                         T temp = array[i];  
  38.                         //后移一位  
  39.                         forint k = i; k > j; k--){  
  40.                             array[k] = array[k-1];  
  41.                         }  
  42.                          array[j] = temp;  
  43.                         break;  
  44.                     }  
  45.                 }  
  46.             }  
  47.         }  
  48.           
  49.         //降序  
  50.         if( direction == 0){  
  51.             forint i=0; i< array.length; i++ ){  
  52.                 for(int j=0; j< i; j ++){  
  53.                     if( array[i].compareTo(array[j]) > 0 ){  
  54.                         T temp = array[i];  
  55.                         //后移一位  
  56.                         forint k = i; k > j; k--){  
  57.                             array[k] = array[k-1];  
  58.                         }  
  59.                         array[j] = temp;  
  60.                         break;  
  61.                     }  
  62.                 }  
  63.             }  
  64.         }  
  65.           
  66.     }  
  67.       
  68.       
  69.     /** 
  70.      * 折半插入排序 
  71.      * 当第i个数插入时,前面i-i个数都已经排好序了,我们没有必要从第一个数开始比较大小; 
  72.      * 我们可以从第(i-i)/2个数开始比较大小, 
  73.      * @param array 
  74.      * @param direction  
  75.      */  
  76.     public void binaryInsertSort(T[] array, int direction){  
  77.           
  78.         int index, position, low, high = 0;  
  79.         T temp;  
  80.         //升序  
  81.         if( direction == 1){  
  82.             for(int i = 1; i< array.length; i++){  
  83.                 low  = 0;  
  84.                 high = i - 1;  
  85.                 temp = array[i];  
  86.                 while(low <= high){  
  87.                     index = (low + high) >> 1;  
  88.                     if( array[i].compareTo(array[index]) > 0 ){  
  89.                         low  = index + 1;  
  90.                     }else if( array[i].compareTo(array[index]) < 0 ){  
  91.                         high = index - 1;  
  92.                     }else{  
  93.                         break;  
  94.                     }  
  95.                 }  
  96.                 position = i;  
  97.                 while(position > low){  
  98.                     array[position] = array[position-1];  
  99.                     position--;  
  100.                 }  
  101.                 array[low] = temp;  
  102.             }  
  103.         }  
  104.           
  105.     }  
  106.       
  107.     /** 
  108.      * 希尔排序 
  109.      * 先取一个正整数d1小于n,把所有序号相隔d1的数组元素放一组,组内进行直接插入排序; 
  110.      * 然后取d2小于d1,重复上述分组和排序操作;直至di=1,即所有记录放进一个组中排序为止 
  111.      * @Description  
  112.      * @param array 需要排序数组 
  113.      * @param direction 0 desc,1 asc; 
  114.      */  
  115.     public void shellSort(T[] array, int direction){  
  116.           
  117.         int len = array.length;  
  118.         int jump = len;  
  119.         T temp;  
  120.         while( jump > 1){  
  121.             jump = jump >> 1;  
  122.             for(int i = 0; i < jump; i++){  
  123.                 //下面属于直接插入排序  
  124.                 forint j = i; j < len; j = j + jump){  
  125.                     for(int k = i; k < j; k = k + jump){  
  126.                        if( direction == 1 ){  
  127.                            if( array[j].compareTo(array[k]) < 0 ){  
  128.                                 temp = array[k];  
  129.                                 array[k] = array[j];  
  130.                                 array[j] = temp;  
  131.                            }  
  132.                        }  
  133.                        else{  
  134.                            if( array[j].compareTo(array[k]) > 0 ){  
  135.                                 temp = array[k];  
  136.                                 array[k] = array[j];  
  137.                                 array[j] = temp;  
  138.                             }  
  139.                        }  
  140.                     }  
  141.                 }  
  142.             }  
  143.         }         
  144.     }  
  145.       
  146.     /** 
  147.      * 冒泡排序 
  148.      *  依次比较相邻的两个数,将小数放在前面,大数放在后面。即在第一趟:首先比较第1个和第2个数,将小数放前,大数放后。 
  149.      *  然后比较第2个数和第3个数,将小数放前,大数放后,如此继续,直至比较最后两个数,将小数放前,大数放后。 
  150.      *  至此第一趟结束,将最大的数放到了最后。 
  151.      *  在第二趟:仍从第一对数开始比较(因为可能由于第2个数和第3个数的交换,使得第1个数不再小于第2个数), 
  152.      *  将小数放前,大数放后,一直比较到倒数第二个数(倒数第一的位置上已经是最大的), 
  153.      *  第二趟结束,在倒数第二的位置上得到一个新的最大数(其实在整个数列中是第二大的数)。 
  154.      *  如此下去,重复以上过程,直至最终完成排序。 
  155.      * @param array 
  156.      * @param direction  
  157.      */  
  158.     public void bubbleSort( T[] array, int direction ){  
  159.           
  160.         int len = array.length;  
  161.         T temp;  
  162.   
  163.             forint i=0; i < len; i++ ){  
  164.                 for(int j = i; j < len - 1; j++ ){  
  165.                     if ( direction == 1 ){  
  166.                         if( array[i].compareTo(array[j + 1]) > 0){  
  167.                             temp = array[i];  
  168.                             array[i] = array[j + 1];  
  169.                             array[j + 1] = temp;  
  170.                         }  
  171.                     }else if( direction == 0 ){  
  172.                         if( array[i].compareTo(array[j + 1]) < 0){  
  173.                             temp = array[i];  
  174.                             array[i] = array[j + 1];  
  175.                             array[j + 1] = temp;  
  176.                         }  
  177.                     }  
  178.                 }  
  179.             }  
  180.     }  
  181.       
  182.     /** 
  183.      * 快速排序 
  184.      * @Description 通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小, 
  185.      * 然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列。 
  186.      * @param array 
  187.      * @param direction , int i,  int j, int direction 
  188.      */  
  189.     public void quickSort( T[] array, int start, int end ){  
  190.           
  191.         int keyIndex  = start;      
  192.         int compIndex = end;  
  193.         T temp;  
  194.         if( end <= start){  
  195.             return;  
  196.         }  
  197.         while(true){  
  198.             if( compIndex  == keyIndex ){  
  199.                 break;  
  200.             }  
  201.             if( array[keyIndex].compareTo(array[compIndex] ) > 0 ){  
  202.                 if( keyIndex < compIndex ){  
  203.                     temp = array[keyIndex];  
  204.                     array[keyIndex] = array[compIndex];  
  205.                     array[compIndex] = temp;  
  206.                     //交换keyIndex与compIndex的值  
  207.                     keyIndex = keyIndex + compIndex;  
  208.                     compIndex = keyIndex - compIndex + 1;  
  209.                     keyIndex = keyIndex - compIndex + 1;  
  210.                 }else{  
  211.                     compIndex = compIndex + 1;  
  212.                 }  
  213.             }else if( array[keyIndex].compareTo(array[compIndex]) < 0 ){  
  214.                 if( keyIndex > compIndex ){  
  215.                     temp = array[keyIndex];  
  216.                     array[ keyIndex ] = array[ compIndex ];  
  217.                     array[ compIndex] = temp;  
  218.                     //交换keyIndex与compIndex的值  
  219.                     keyIndex = keyIndex + compIndex;  
  220.                     compIndex = keyIndex - compIndex - 1;  
  221.                     keyIndex = keyIndex - compIndex - 1;  
  222.                 }else{  
  223.                     compIndex = compIndex - 1;  
  224.                 }  
  225.             }else{  
  226.                 if( keyIndex < compIndex ){  
  227.                     //交换keyIndex与compIndex的值  
  228.                     keyIndex = keyIndex + compIndex;  
  229.                     compIndex = keyIndex - compIndex + 1;  
  230.                     keyIndex = keyIndex - compIndex + 1;  
  231.                 }else{  
  232.                     //交换keyIndex与compIndex的值  
  233.                     keyIndex = keyIndex + compIndex;  
  234.                     compIndex = keyIndex - compIndex - 1;  
  235.                     keyIndex = keyIndex - compIndex - 1;  
  236.                 }  
  237.             }  
  238.         }  
  239.           
  240.         //递归  
  241.         quickSort(array, start, keyIndex - 1 );  
  242.         quickSort(array, keyIndex + 1, end );  
  243.     }      
  244.   
  245.       
  246.     /** 
  247.      * @Description 直接选择排序  
  248.      *  和冒泡排序类似,莫要混淆了 
  249.      * 第一次从R[0]~R[n-1]中选取最小值,与R[0]交换,第二次从R{1}~R[n-1]中选取最小值,与R[1]交换,...., 
  250.      * 第i次从R[i-1]~R[n-1]中选取最小值,与R[i-1]交换,.....,第n-1次从R[n-2]~R[n-1]中选取最小值,与R[n-2]交换, 
  251.      * 总共通过n-1次,得到一个按排序码从小到大排列的有序序列. 
  252.      * 冒泡排序每一次比较都有可能交换值;这个需要记住每一趟最大值或者最小值的位置 
  253.      * @param array  
  254.      * @param direction  
  255.      */  
  256.     public void straightSelectSort(T[] array, int direction){  
  257.           
  258.         int len = array.length;  
  259.         T mTempData;  
  260.         int change_index;  
  261.         forint i = 0; i < len; i++ ){  
  262.             mTempData = array[i];  
  263.             change_index = i;  
  264.             forint j = i; j < len; j++ ){  
  265.                 if( mTempData.compareTo(array[j]) > 0){  
  266.                     mTempData = array[j];  
  267.                     change_index = j;//记住最大值的位置  
  268.                 }  
  269.             }  
  270.             array[change_index] = array[i];  
  271.             array[i] = mTempData;  
  272.         }  
  273.           
  274.     }  
  275.       
  276.       
  277.     /** 
  278.      * 最大堆 
  279.      * @param array 
  280.      * @param i  
  281.      */  
  282.     public void maxHeapify( T[] array, int i){  
  283.           
  284.         int left = 2*i+1;    
  285.         int right = 2*i+2;    
  286.         int max = i;   
  287.           
  288.         //先判断左子节点    
  289.         if( left < array.length && array[max].compareTo(array[left]) < 0 ){  
  290.             max = left;  
  291.         }  
  292.           
  293.         //需要确定右子节点是否存在    
  294.         if( right < array.length && array[max].compareTo(array[right]) < 0 ){  
  295.             max = right;  
  296.         }  
  297.           
  298.         if( max != i ){  
  299.             //System.out.println("swap");  
  300.             T tmp = array[max];  
  301.             array[max] = array[i];  
  302.             array[i] = tmp;  
  303.             maxHeapify(array, max);  
  304.         }  
  305.     }  
  306.   
  307.       
  308.     /** 
  309.      * 最小堆 
  310.      * @param array 
  311.      * @param i  
  312.      */  
  313.     public void minHeapify( T[] array, int i){  
  314.           
  315.         int left = 2*i+1;  
  316.         int right = 2*i+2;  
  317.         int max = i;  
  318.           
  319.         //先判断左子节点  
  320.         if(  left < array.length && array[max].compareTo(array[left]) > 0 ){  
  321.             max = left;  
  322.         }  
  323.           
  324.         //需要确定右子节点是否存在    
  325.         if( right < array.length && array[max].compareTo(array[right]) > 0 ){  
  326.             max = right;  
  327.         }  
  328.           
  329.         if( max != i ){  
  330.             //System.out.println("swap");  
  331.             T tmp = array[max];  
  332.             array[max] = array[i];  
  333.             array[i] = tmp;  
  334.             minHeapify(array, max);  
  335.         }  
  336.     }  
  337.       
  338.       
  339.       
  340.     /** 
  341.      * 创建堆 
  342.      * 堆从逻辑上讲是一种非线性结构,但实际中我们使用线性结构来存储;堆首先是一个完全二叉树,根节点的值是最大值(最小值) 
  343.      * @param array 
  344.      */  
  345.     public void createHeap( T[] array ){  
  346.           
  347.         int len = (array.length-1)/2;  
  348.           
  349.         for ( int i = len; i >= 0; i-- ){  
  350.             //maxHeapify(array, i);  
  351.             minHeapify(array, i);  
  352.         }  
  353.     }  
  354.       
  355.     /** 
  356.      * 堆排序 
  357.      *   
  358.      * @param array 
  359.      * @param direction 
  360.      */  
  361.     public T[] heapSort(T[] array,T[] result, int direction){  
  362.           
  363.         int index = 0;  
  364.         int len = array.length;  
  365.         //取出堆顶,重复建堆  
  366.         for ( int i = len-1; i >= 0; i-- ){  
  367.             result[index] = array[0];  
  368.             index++;  
  369.             array[0] = array[array.length-1];  
  370.             array = Arrays.copyOfRange(array, 0, i);  
  371.             minHeapify(array, 0);  
  372.             //maxHeapify(array, 0);  
  373.         }  
  374.         return result;  
  375.     }  
  376.       
  377.     public void merge ( T[] array, int low, int mid, int high){  
  378.         //T[] tempArr = new Object<T>[high - low];  
  379.         List<T> tempList = new LinkedList<T>();  
  380.         int s1 = low;  
  381.         int s2 = mid + 1;  
  382.         while( s1 <= mid && s2 <= high ){  
  383.             if( array[s1].compareTo(array[s2]) <= 0){  
  384.                 tempList.add(array[s1++]);  
  385.             }else{  
  386.                 tempList.add(array[s2++]);  
  387.             }  
  388.         }  
  389.           
  390.         if(s1 <= mid){  
  391.             for(int i=s1; i <= mid; i++){  
  392.                 tempList.add(array[i]);  
  393.             }  
  394.         }  
  395.           
  396.         if(s2 <= high){  
  397.             for(int i=s2; i <= high; i++){  
  398.                 tempList.add(array[i]);  
  399.             }  
  400.         }  
  401.           
  402.         Object[] arrayList =  tempList.toArray();  
  403.         System.out.println(Arrays.toString(arrayList) + low + ":" + high);  
  404.         for (int i=0;i<arrayList.length;i++){  
  405.             array[low + i] = (T)arrayList[i];  
  406.         }  
  407.         tempList.clear();  
  408.     }  
  409.       
  410.     /** 
  411.      * 归并排序 
  412.      * @param array 
  413.      * @param low 
  414.      * @param high  
  415.      */  
  416.     public void mergeSort( T[] array,int low, int high){  
  417.         //int len = array.length;  
  418.         if (low < high){  
  419.             mergeSort(array, low, (low + high)/2);  
  420.             mergeSort(array, (low + high)/2 + 1, high);  
  421.             merge(array, low, (low + high)/2, high);  
  422.         }  
  423.           
  424.     }  
  425.       
  426.     public static void main(String[] args){  
  427.           
  428.         SortPractice sort = new SortPractice();  
  429.           
  430.         Integer num01 = new Integer(12);  
  431.         Integer num02 = new Integer(13);  
  432.         Integer num03 = new Integer(44);  
  433.         Integer num04 = new Integer(3);  
  434.         Integer num05 = new Integer(13);  
  435.         Integer num06 = new Integer(5);  
  436.         Integer num07 = new Integer(7);  
  437.           
  438.         Integer[] array = {num01, num02, num03, num04, num05, num06, num07, num04};  
  439.         //Integer[] result = new Integer[array.length];  
  440.         //sort.directInsertSort(array, 1);  
  441.         //sort.binaryInsertSort(array, 1);  
  442.         //sort.shellSort(array, 1);  
  443.         System.out.println(Arrays.toString(array));  
  444.         sort.mergeSort(array, 0, array.length - 1);  
  445.         //sort.bubbleSort(array, 1);  
  446.         //sort.quickSort(array, 0, array.length - 1);  
  447.         //sort.createHeap(array);  
  448.         System.out.println(Arrays.toString(array));  
  449.         //sort.heapSort(array, result, 1);  
  450.         //System.out.println(Arrays.toString(result));  
  451.         /*for( int i=0; i < array.length; i++ ){ 
  452.             System.out.println( array[i] ); 
  453.         }*/  
  454.           
  455.     }  
  456. }  

 还有基数排序未实现。

分享到:
评论

相关推荐

    Java各种排序算法代码.zip

    这个名为"Java各种排序算法代码.zip"的压缩包包含了一系列实现不同排序算法的Java源代码。排序算法是计算机科学中的基本概念,用于对一组数据进行排列。下面将详细讨论这些算法及其在Java中的实现。 1. 冒泡排序...

    Java各种排序算法

    本文将详细介绍几种常见的Java排序算法,包括它们的工作机制、优缺点以及适用场景。 1. 插入排序 - 直接插入排序:该算法通过将每个元素插入到已排序部分的正确位置来工作。在Java中,可以通过遍历数组,将每个...

    Java各种排序算法(含代码)

    在编程领域,排序算法是数据结构与算法学习中的基础部分,尤其在Java中,了解和掌握各种排序算法对于提升程序性能至关重要。以下是对标题和描述中提到的Java各种排序算法的详细解释,以及它们的实现代码概述。 1)*...

    java各种排序算法

    Java作为广泛应用的编程语言,提供了丰富的工具和方法来实现各种排序算法。以下是对标题"java各种排序算法"和描述中涉及的知识点的详细说明。 1. **冒泡排序(Bubble Sort)** 冒泡排序是最基础的排序算法之一,通过...

    Java各种排序算法Demo

    本资料包"Java各种排序算法Demo"聚焦于通过Java代码展示不同的排序算法,旨在帮助开发者理解和应用这些算法。 首先,我们来探讨几种基础的排序算法: 1. **冒泡排序**:冒泡排序是一种简单的排序算法,通过重复...

    面试最常见的问题(java各种排序法)

    以下是对"面试最常见的问题(java各种排序法)"这一主题的详细解释。 首先,我们来了解一下排序的基本定义:排序是将一组数据按照特定顺序进行排列的过程。在计算机科学中,这通常指的是对数组或列表等数据结构中的...

    java各种排序算法总结

    所谓排序,就是使一串记录,按照其中的某个或某些关键字的大小,递增或递减的排列起来的操作。...在各个领域中考虑到数据的各种限制和规范,要得到一个符合实际的优秀算法,得经过大量的推理和分析。

    Java各种排序算法代码

    Java作为一种广泛使用的编程语言,提供了丰富的工具和方法来实现各种排序算法。本篇将详细讲解标题为"Java各种排序算法代码"的知识点,这些代码案例不仅完整,而且能够运行,非常适合学习和实践。 1. 冒泡排序...

    Java各种排序算法、Java游戏和实例代码集合

    在这个"Java各种排序算法、Java游戏和实例代码集合"中,我们可以深入学习Java编程的核心技术,并通过实践加强理解。以下是一些关键知识点的详细说明: 1. **排序算法**: - **冒泡排序**:是最基础的排序算法之一...

    java各种排序算法源码

    本资源"java各种排序算法源码"涵盖了六种常见的排序算法,它们分别是:直接插入排序、希尔排序、冒泡排序、快速排序、直接选择排序和堆排序。接下来,我们将详细探讨这些排序算法的基本原理、特点以及在Java中的实现...

    Java各种排序算法代码.7z

    这里,我们将深入探讨一些常见的Java排序算法,包括它们的工作原理、优缺点以及适用场景。 1. 冒泡排序(Bubble Sort): 冒泡排序是一种简单的交换排序,通过重复遍历数组,比较相邻元素并根据需要交换它们,直到...

    java各种排序算法实现

    java各种排序算法实现,仅供参考。java各种排序算法实现,仅供参考。

    JAVA各种排序方法及改良

    本文将深入探讨Java中的各种排序方法以及它们的改良策略。首先,我们来看看几种基础的排序算法,然后讨论如何通过优化来提高这些算法的性能。 1. **冒泡排序**(Bubble Sort): 冒泡排序是最基础的排序算法之一,...

Global site tag (gtag.js) - Google Analytics