排序算法(Java)

2019-11-06 06:24:41

字体：大中小

来源：转载

供稿：网友

选择排序

基本思想:从a[i]右边找到最小的数,与a[i]交换

void sort(Comparable[] a){ int n = a.length; for(int i=0; i<a.length; i++){ int min = i; for(int j=i+1; j<a.length; j++){ if(less(a[j],a[min])) min = j; } exch(a,i,j); }}

冒泡排序

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

void sort(Comparable[] a){ int n = a.length; for(int i=n-1; i>0; i--){ for(int j=n-1; j>0; j--){ if(less(a[j],a[j-1])) exch(a,j,j-1); } } }

插入排序

基本思想:将一个记录插入到已排序好的有序表中，从而得到一个新，记录数增1的有序表

void sort(Comparable[] a){ int n = a.length; for(int i=0; i<a.length; i++){ for(int j=i+1; j>0&&less(a[j],[j-1]); j--){ exch(a,j,j-1); } }}

希尔排序

基本思想:先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录“基本有序”时，再对全体记录进行依次直接插入排序。又叫缩小增量排序。

void sort(Comparable[] a){ int n = a.length; int h = 1;//增量 while(h<n/3) h = 3*h+1;//1,4,13,... while(h>=1){ for(int i=h; i<a.length; i++){ for(int j=i+h; j>h&&less(a[j],[j-h]); j-=h){ exch(a,j,j-h); } } h = h/3; } }

快速排序

基本思想:一种分治的排序算法,将一个数组分成两个子数组,将两部分独立排序

1）选择一个基准元素,通常选择第一个元素或者最后一个元素, 2）通过一趟排序讲待排序的记录分割成独立的两部分，其中一部分记录的元素值均比基准元素值小。另一部分记录的元素值比基准值大。 3）此时基准元素在其排好序后的正确位置 4）然后分别对这两部分记录用同样的方法继续进行排序，直到整个序列有序。

//快速排序public static void sort(Comparable[] a){ int n = a.length; sort(a, 0, n-1); }PRivate static void sort(Comparable[] a, int lo, int hi){ if(lo>=hi) return; int j = partition(a, lo, hi); sort(a, lo, j-1); sort(a, j+1, hi); }private static int partition(Comparable[] a, int lo, int hi){ int i = lo, j = hi+1; Comparable v = a[lo]; while(true){ while(less(a[++i], v)) if(i==hi) break; while(less(v, a[--j])) if(j==lo) break; if(i>=j) break; exch(a,i,j); } exch(a,lo,j); return j; }//重复元素较多时,三向切分的快速排序public static void sort(Comparable[] a){ int n = a.length; sort(a, 0, n-1); }private static void sort(Comparable[] a, int lo, int hi){ if(lo>=hi) return; int lt = lo, i = lo+1; gt = hi; Comparable v = a[lo]; while(i<=gt){ int cmp = a[i].comparaTo(v); if(cmp<0) exch(a, lt++; i++); else(cmp>0) exch(a, i, gt--); else i++; } sort(a, lo, lt-1); sort(a, gt+1, hi); }

归并排序

基本思想:归并（Merge）排序法是将两个（或两个以上）有序表合并成一个新的有序表

//自顶向下的归并排序public static void sort(Comparable[] a) { aux = new Comparable[a.length]; sort(a, 0, a.length-1); }private static void sort(Comparable[] a, int lo, int hi){ if(hi<=lo) return; int mid = (lo+hi)/2; sort(a, lo, mid); sort(a, mid+1, hi); merge(a,lo,mid,hi); }public static void merge(Comparable[] a, int lo, int mid, int hi) { int i = lo, j = mid + 1; for (int k = lo; k <= hi; k++) aux[k] = a[k]; //复制 for (int k = lo; k <= hi; k++) { //归并 if (i > mid) a[k] = aux[j++]; else if (j > hi) a[k] = aux[i++]; else if (less(aux[j], aux[i])) a[k] = aux[j++]; else a[k] = aux[i++]; } }//自底向上的归并排序public static void sort(Comparable[] a) { int n = a.length; aux = new Comparable[n]; for( int sz=1; sz<n; sz=sz+sz){ for(int lo=0; lo<n-sz; lo+=sz+sz){ merge(a, lo, lo+sz-1, Math.min(lo+sz+sz-1, n-1)); } } }public static void merge(Comparable[] a, int lo, int mid, int hi) { int i = lo, j = mid + 1; for (int k = lo; k <= hi; k++) aux[k] = a[k]; //复制 for (int k = lo; k <= hi; k++) { //归并 if (i > mid) a[k] = aux[j++]; else if (j > hi) a[k] = aux[i++]; else if (less(aux[j], aux[i])) a[k] = aux[j++]; else a[k] = aux[i++]; } }

堆排序

基本思想堆的定义如下：具有n个元素的序列（k1,k2,…,kn),当且仅当满足这里写图片描述

时称之为堆。由堆的定义可以看出，堆顶元素（即第一个元素）必为最小项（小顶堆）。若以一维数组存储一个堆，则堆对应一棵完全二叉树，且所有非叶结点的值均不大于(或不小于)其子女的值，根结点（堆顶元素）的值是最小(或最大)的。

public static void sort(Comparable[] a){ int n = a.length; for(int k=n/2; k>=1; k--) sink(a,k,n); while(n>1){ exch(a,1,--n); sink(a,1,n); } } private static void sink(Comparable[] a, int k, int n){ while(2*k<=n-2){ int j = 2*k; if(j<n && less(a[j], a[j+1])) j++; if(!less(a[k],a[j])) break; exch(a,k,j); k = j; } }

上一篇：深入理解Java：内部类

下一篇：java从头开始学习到选择c++ （二）java概述（2）