java 排序算法大全

hao2181 贡献于2012-10-09

作者 雨林木风  创建于2010-04-07 23:16:00   修改者微软系统  修改于2010-06-01 08:58:00字数17189

文档摘要:一插入排序该算法在数据规模小的时候十分高效,该算法每次插入第K+1到前K个有序数组中一个合适位置,K从0开始到N-1,从而完成排序;二冒泡排序这可能是最简单的排序算法了,算法思想是每次从数组末端开始比较相邻两元素,把第i小的冒泡到数组的第i个位置。i从0一直到N-1从而完成排序。
关键词:

java排序算法大全 为了便于管理,先引入个基础类: package algorithms; public abstract class Sorter> {          public abstract void sort(E[] array,int from ,int len);          public final void sort(E[] array)     {         sort(array,0,array.length);     }     protected final void swap(E[] array,int from ,int to)     {         E tmp=array[from];         array[from]=array[to];         array[to]=tmp;     } } 一 插入排序 该算法在数据规模小的时候十分高效,该算法每次插入第K+1到前K个有序数组中一个合适位置,K从0开始到N-1,从而完成排序: package algorithms; /**  * @author yovn  */ public class InsertSorter> extends Sorter {     /* (non-Javadoc)      * @see algorithms.Sorter#sort(E[], int, int)      */     public void sort(E[] array, int from, int len) {          E tmp=null;           for(int i=from+1;ifrom;j--)               {                   if(tmp.compareTo(array[j-1])<0)                   {                       array[j]=array[j-1];                   }                   else break;               }               array[j]=tmp;           }     }               } 二 冒泡排序 这可能是最简单的排序算法了,算法思想是每次从数组末端开始比较相邻两元素,把第i小的冒泡到数组的第i个位置。i从0一直到N-1从而完成排序。(当然也可以从数组开始端开始比较相邻两元素,把第i大的冒泡到数组的第N-i个位置。i从0一直到N-1从而完成排序。) package algorithms; /**  * @author yovn  *  */ public class BubbleSorter> extends Sorter {     private static  boolean DWON=true;          public final void bubble_down(E[] array, int from, int len)     {         for(int i=from;ii;j--)             {                 if(array[j].compareTo(array[j-1])<0)                 {                     swap(array,j-1,j);                 }             }         }     }          public final void bubble_up(E[] array, int from, int len)     {         for(int i=from+len-1;i>=from;i--)         {             for(int j=from;j0)                 {                     swap(array,j,j+1);                 }             }         }     }     @Override     public void sort(E[] array, int from, int len) {                  if(DWON)         {             bubble_down(array,from,len);         }         else         {             bubble_up(array,from,len);         }     }      } 三,选择排序 选择排序相对于冒泡来说,它不是每次发现逆序都交换,而是在找到全局第i小的时候记下该元素位置,最后跟第i个元素交换,从而保证数组最终的有序。 相对与插入排序来说,选择排序每次选出的都是全局第i小的,不会调整前i个元素了。 package algorithms; /**  * @author yovn  *  */ public class SelectSorter> extends Sorter {     /* (non-Javadoc)      * @see algorithms.Sorter#sort(E[], int, int)      */     @Override     public void sort(E[] array, int from, int len) {         for(int i=0;i> extends Sorter  {     /* (non-Javadoc)      * Our delta value choose 2^k-1,2^(k-1)-1,.7,3,1.      * complexity is O(n^1.5)      * @see algorithms.Sorter#sort(E[], int, int)      */     @Override      public void sort(E[] array, int from, int len) {                  //1.calculate  the first delta value;         int value=1;         while((value+1)*2=1;delta=(delta+1)/2-1)         {             for(int i=0;ifrom;j-=delta)               {                   if(tmp.compareTo(array[j-delta])<0)                   {                       array[j]=array[j-delta];                   }                   else break;               }               array[j]=tmp;           }     } } 五 快速排序 快速排序是目前使用可能最广泛的排序算法了。 一般分如下步骤: 1)选择一个枢纽元素(有很对选法,我的实现里采用去中间元素的简单方法) 2)使用该枢纽元素分割数组,使得比该元素小的元素在它的左边,比它大的在右边。并把枢纽元素放在合适的位置。 3)根据枢纽元素最后确定的位置,把数组分成三部分,左边的,右边的,枢纽元素自己,对左边的,右边的分别递归调用快速排序算法即可。 快速排序的核心在于分割算法,也可以说是最有技巧的部分。 package algorithms; /**  * @author yovn  *  */ public class QuickSorter> extends Sorter {     /* (non-Javadoc)      * @see algorithms.Sorter#sort(E[], int, int)      */     @Override     public void sort(E[] array, int from, int len) {         q_sort(array,from,from+len-1);     }          private final void q_sort(E[] array, int from, int to) {         if(to-from<1)return;         int pivot=selectPivot(array,from,to);                           pivot=partion(array,from,to,pivot);                  q_sort(array,from,pivot-1);         q_sort(array,pivot+1,to);              }     private int partion(E[] array, int from, int to, int pivot) {         E tmp=array[pivot];         array[pivot]=array[to];//now to's position is available                  while(from!=to)         {              while(from=0)to--;             if(from> extends Sorter  {     /* (non-Javadoc)      * @see algorithms.Sorter#sort(E[], int, int)      */     @SuppressWarnings("unchecked")     @Override     public void sort(E[] array, int from, int len) {         if(len<=1)return;         E[] temporary=(E[])Array.newInstance(array[0].getClass(),len);         merge_sort(array,from,from+len-1,temporary);     }     private final void merge_sort(E[] array, int from, int to, E[] temporary) {         if(to<=from)         {             return;         }         int middle=(from+to)/2;         merge_sort(array,from,middle,temporary);         merge_sort(array,middle+1,to,temporary);         merge(array,from,to,middle,temporary);     }     private final void merge(E[] array, int from, int to, int middle, E[] temporary) {         int k=0,leftIndex=0,rightIndex=to-from;         System.arraycopy(array, from, temporary, 0, middle-from+1);         for(int i=0;i> extends Sorter  {     /* (non-Javadoc)      * @see algorithms.Sorter#sort(E[], int, int)      */     @Override     public void sort(E[] array, int from, int len) {         build_heap(array,from,len);         for(int i=0;i=0;i--)         {             shift_down(array,from,len,i);         }              }           private final void shift_down(E[] array,int from, int len, int pos)     {                  E tmp=array[from+pos];         int index=pos*2+1;//use left child         while(index=0;k--)//from the ending to beginning can keep the stability         {             keys[--count[temp[k]]]=temp[k];// position +1 =count         }     }     /**      * @param args      */     public static void main(String[] args) {         int[] a={1,4,8,3,2,9,5,0,7,6,9,10,9,13,14,15,11,12,17,16};         BucketSorter sorter=new BucketSorter();         sorter.sort(a,0,a.length,20);//actually is 18, but 20 will also work                           for(int i=0;i=0;m--)             {                 int subkey=(temporary[m]/R)%radix;                 --count[subkey];                 keys[from+count[subkey]]=temporary[m];             }             R*=radix;         }                 }      private static class LinkQueue     {         int head=-1;         int tail=-1;     }     private final void link_radix_sort(int[] keys, int from, int len, int radix, int d) {                  int[] nexts=new int[len];                  LinkQueue[] queues=new LinkQueue[radix];         for(int i=0;i data[j + 1]) { //交换相邻两个数 swap(data, j, j + 1); } } } } else if (sortType.equals("desc")) { //倒排序,从大排到小 //比较的轮数 for (int i = 1; i < data.length; i++) { //将相邻两个数进行比较,较大的数往后冒泡 for (int j = 0; j < data.length - i; j++) { if (data[j] < data[j + 1]) { //交换相邻两个数 swap(data, j, j + 1); } } } } else { System.out.println("您输入的排序类型错误!"); } printArray(data);//输出冒泡排序后的数组值 } /** * 直接选择排序法----选择排序的一种 * 方法:每一趟从待排序的数据元素中选出最小(或最大)的一个元素, 顺序放在已排好序的数列的最后,直到全部待排序的数据元素排完。 * 性能:比较次数O(n^2),n^2/2 * 交换次数O(n),n * 交换次数比冒泡排序少多了,由于交换所需CPU时间比比较所需的CUP时间多,所以选择排序比冒泡排序快。 * 但是N比较大时,比较所需的CPU时间占主要地位,所以这时的性能和冒泡排序差不太多,但毫无疑问肯定要快些。 * * @param data 要排序的数组 * @param sortType 排序类型 * @return */ public void selectSort(int[] data, String sortType) { if (sortType.equals("asc")) { //正排序,从小排到大 int index; for (int i = 1; i < data.length; i++) { index = 0; for (int j = 1; j <= data.length - i; j++) { if (data[j] > data[index]) { index = j; } } //交换在位置data.length-i和index(最大值)两个数 swap(data, data.length - i, index); } } else if (sortType.equals("desc")) { //倒排序,从大排到小 int index; for (int i = 1; i < data.length; i++) { index = 0; for (int j = 1; j <= data.length - i; j++) { if (data[j] < data[index]) { index = j; } } //交换在位置data.length-i和index(最大值)两个数 swap(data, data.length - i, index); } } else { System.out.println("您输入的排序类型错误!"); } printArray(data);//输出直接选择排序后的数组值 } /** * 插入排序 * 方法:将一个记录插入到已排好序的有序表(有可能是空表)中,从而得到一个新的记录数增1的有序表。 * 性能:比较次数O(n^2),n^2/4 * 复制次数O(n),n^2/4 * 比较次数是前两者的一般,而复制所需的CPU时间较交换少,所以性能上比冒泡排序提高一倍多,而比选择排序也要快。 * * @param data 要排序的数组 * @param sortType 排序类型 */ public void insertSort(int[] data, String sortType) { if (sortType.equals("asc")) { //正排序,从小排到大 //比较的轮数 for (int i = 1; i < data.length; i++) { //保证前i+1个数排好序 for (int j = 0; j < i; j++) { if (data[j] > data[i]) { //交换在位置j和i两个数 swap(data, i, j); } } } } else if (sortType.equals("desc")) { //倒排序,从大排到小 //比较的轮数 for (int i = 1; i < data.length; i++) { //保证前i+1个数排好序 for (int j = 0; j < i; j++) { if (data[j] < data[i]) { //交换在位置j和i两个数 swap(data, i, j); } } } } else { System.out.println("您输入的排序类型错误!"); } printArray(data);//输出插入排序后的数组值 } /** * 反转数组的方法 * @param data 源数组 */ public void reverse(int[] data) { int length = data.length; int temp = 0;//临时变量 for (int i = 0; i < length / 2; i++) { temp = data[i]; data[i] = data[length - 1 - i]; data[length - 1 - i] = temp; } printArray(data);//输出到转后数组的值 } /** * 快速排序 * 快速排序使用分治法(Divide and conquer)策略来把一个序列(list)分为两个子序列(sub-lists)。 * 步骤为: * 1. 从数列中挑出一个元素,称为 "基准"(pivot), * 2. 重新排序数列,所有元素比基准值小的摆放在基准前面,所有元素比基准值大的摆在基准的后面(相同的数可以到任一边)。在这个分割之后,该基准是它的最后位置。这个称为分割(partition)操作。 * 3. 递归地(recursive)把小于基准值元素的子数列和大于基准值元素的子数列排序。 * 递回的最底部情形,是数列的大小是零或一,也就是永远都已经被排序好了。虽然一直递回下去,但是这个算法总会结束,因为在每次的迭代(iteration)中,它至少会把一个元素摆到它最后的位置去。 * @param data 待排序的数组 * @param low * @param high * @see SortTest#qsort(int[], int, int) * @see SortTest#qsort_desc(int[], int, int) */ public void quickSort(int[] data, String sortType) { if (sortType.equals("asc")) { //正排序,从小排到大 qsort_asc(data, 0, data.length - 1); } else if (sortType.equals("desc")) { //倒排序,从大排到小 qsort_desc(data, 0, data.length - 1); } else { System.out.println("您输入的排序类型错误!"); } } /** * 快速排序的具体实现,排正序 * @param data * @param low * @param high */ private void qsort_asc(int data[], int low, int high) { int i, j, x; if (low < high) { //这个条件用来结束递归 i = low; j = high; x = data[i]; while (i < j) { while (i < j && data[j] > x) { j--; //从右向左找第一个小于x的数 } if (i < j) { data[i] = data[j]; i++; } while (i < j && data[i] < x) { i++; //从左向右找第一个大于x的数 } if (i < j) { data[j] = data[i]; j--; } } data[i] = x; qsort_asc(data, low, i - 1); qsort_asc(data, i + 1, high); } } /** * 快速排序的具体实现,排倒序 * @param data * @param low * @param high */ private void qsort_desc(int data[], int low, int high) { int i, j, x; if (low < high) { //这个条件用来结束递归 i = low; j = high; x = data[i]; while (i < j) { while (i < j && data[j] < x) { j--; //从右向左找第一个小于x的数 } if (i < j) { data[i] = data[j]; i++; } while (i < j && data[i] > x) { i++; //从左向右找第一个大于x的数 } if (i < j) { data[j] = data[i]; j--; } } data[i] = x; qsort_desc(data, low, i - 1); qsort_desc(data, i + 1, high); } } /** *二分查找特定整数在整型数组中的位置(递归) *查找线性表必须是有序列表 *@paramdataset *@paramdata *@parambeginIndex *@paramendIndex *@returnindex */ public int binarySearch(int[] dataset, int data, int beginIndex, int endIndex) { int midIndex = (beginIndex + endIndex) >>> 1; //相当于mid = (low + high) / 2,但是效率会高些 if (data < dataset[beginIndex] || data > dataset[endIndex] || beginIndex > endIndex) return -1; if (data < dataset[midIndex]) { return binarySearch(dataset, data, beginIndex, midIndex - 1); } else if (data > dataset[midIndex]) { return binarySearch(dataset, data, midIndex + 1, endIndex); } else { return midIndex; } } /** *二分查找特定整数在整型数组中的位置(非递归) *查找线性表必须是有序列表 *@paramdataset *@paramdata *@returnindex */ public int binarySearch(int[] dataset, int data) { int beginIndex = 0; int endIndex = dataset.length - 1; int midIndex = -1; if (data < dataset[beginIndex] || data > dataset[endIndex] || beginIndex > endIndex) return -1; while (beginIndex <= endIndex) { midIndex = (beginIndex + endIndex) >>> 1; //相当于midIndex = (beginIndex + endIndex) / 2,但是效率会高些 if (data < dataset[midIndex]) { endIndex = midIndex - 1; } else if (data > dataset[midIndex]) { beginIndex = midIndex + 1; } else { return midIndex; } } return -1; } public static void main(String[] args) { SortTest sortTest = new SortTest(); int[] array = sortTest.createArray(); System.out.println("==========冒泡排序后(正序)=========="); sortTest.bubbleSort(array, "asc"); System.out.println("==========冒泡排序后(倒序)=========="); sortTest.bubbleSort(array, "desc"); array = sortTest.createArray(); System.out.println("==========倒转数组后=========="); sortTest.reverse(array); array = sortTest.createArray(); System.out.println("==========选择排序后(正序)=========="); sortTest.selectSort(array, "asc"); System.out.println("==========选择排序后(倒序)=========="); sortTest.selectSort(array, "desc"); array = sortTest.createArray(); System.out.println("==========插入排序后(正序)=========="); sortTest.insertSort(array, "asc"); System.out.println("==========插入排序后(倒序)=========="); sortTest.insertSort(array, "desc"); array = sortTest.createArray(); System.out.println("==========快速排序后(正序)=========="); sortTest.quickSort(array, "asc"); sortTest.printArray(array); System.out.println("==========快速排序后(倒序)=========="); sortTest.quickSort(array, "desc"); sortTest.printArray(array); System.out.println("==========数组二分查找=========="); System.out.println("您要找的数在第" + sortTest.binarySearch(array, 74) + "个位子。(下标从0计算)"); } }

下载文档到电脑,查找使用更方便

文档的实际排版效果,会与网站的显示效果略有不同!!

需要 8 金币 [ 分享文档获得金币 ] 0 人已下载

下载文档