经典排序算法(Java实现)

以下程序均将数据封装于DataWrap数据包装类中,如下所示:

经典排序算法(Java实现)
 1 //数据包装类
 2      class DataWrap implements Comparable<DataWrap>
 3      {
 4         int data;
 5         String flag;
 6         public DataWrap(int data,String flag)
 7         {
 8             this.data = data;
 9             this.flag = flag;
10         }
11         //重写compareTo方法
12         public int compareTo(DataWrap other)
13         {
14             return this.data > other.data ? 1 : (this.data == other.data ? 0 : -1);
15         }
16         public String toString()
17         {
18             return this.data + this.flag;
19         }
20     }
View Code

 

一、选择排序

1、直接选择排序

  数组分成有序区和无序区,初始时整个数组都是无序区,然后每次从无序区选一个最小的元素直接放到有序区的最后,直到整个数组变有序区。

经典排序算法(Java实现)
 1 public static void directSelectSort(DataWrap[] dw)
 2     {
 3         int n = dw.length;
 4         for(int i = 0;i < n-1;i++)
 5         {
 6             int minIndex = i;  
 7             for(int j = i+1;j < n;j++)
 8             {
 9                 if(dw[minIndex].compareTo(dw[j]) > 0)
10                 {
11                     minIndex = j;  //minIndex为每趟比较重最小数的索引
12                 }
13             }
14             swap(dw,minIndex,i);
15             System.out.println("直接选择排序中的元素:" + Arrays.toString(dw));
16         }
17         
18     }
View Code

2、堆排序

  1)二叉堆

    二叉堆是完全二叉树或者是近似完全二叉树。

    父结点的键值总是大于或等于(小于或等于)任何一个子节点的键值。

    每个结点的左子树和右子树都是一个二叉堆(都是最大堆或最小堆)。

   当父结点的键值总是大于或等于任何一个子节点的键值时为最大堆。当父结点的键值总是小于或等于任何一个子节点的键值时为最小堆。

  2)堆的存储

    一般都用数组来表示堆,i结点的父结点下标就为(i – 1) / 2。它的左右子结点下标分别为2 * i + 1和2 * i + 2。如第0个结点左右子结点下标分别为1和2。

   3)堆排序原理(以最小堆为例)

    堆排序是先建立一个最小堆,然后第一次将A[0]与A[n - 1]交换,再对A[0…n-2]重新恢复最小堆。第二次将A[0]与A[n – 2]交换,再对A[0,…,n - 3]重新

  恢复最小堆,重复这样的操作直到A[0]与A[1]交换。由于每次都是将最小的数据并入到后面的有序区间,故操作完成后整个数组就有序(为降序)了。

建立最小堆就是先从最后一个非叶子节点(即n/2-1节点)开始,节点依次往前就行,直到第二个节点。对于每个节点,先比较其左右节点选出较小的节点,然后

将较小的节点与父节点进行比较。如果父节点比最小的子节点还小的话则不需要调整,否则的话将较小的子节点作为新的父节点,将原先的父节点与其子节点的子节

点中较小的进行比较,直到该父节点找到能够插入的位置或者是到达堆的结束。

  4)代码实现

经典排序算法(Java实现)
 1 public class HeapSort 
 2 {
 3     /**
 4      * 从某一节点向下调整大小  
 5      * @param dw 待排序数据包
 6      * @param i     开始向下调整的堆索引
 7      * @param n  所调整堆数据的大小
 8      */
 9     public static void MinHeapFixDown(DataWrap[] dw,int i,int n)
10     {
11         int j;
12         DataWrap temp;
13         j = 2 * i +1;
14         temp = dw[i];
15         while(j < n)
16         {
17             if(j+1 < n && dw[j+1].compareTo(dw[j]) < 0)
18             { //找出左右子节点中较小的
19                 j++;
20             }
21             if(temp.compareTo(dw[j]) <= 0)
22             {  //将父节点与子节点进行比较
23                 break;
24             }
25             dw[i] = dw[j];  //将较小的子节点上移
26             i = j;
27             j = 2 * i +1;
28         }
29         dw[i] = temp; 
30     }
31     //构建最小堆并进行堆排序
32     public static void heapSort(DataWrap[] dw)
33     {
34         int n = dw.length;
35         //构建最小堆
36         for(int i = n/2-1;i >= 1;i--)
37         {
38             HeapSort.MinHeapFixDown(dw, i, n);
39         }
40         //堆排序
41         for(int i = n-1;i >=1;i--)
42         {  
43             swap(dw,0,i);   //每次将第n-1,n-2,...1个元素与dw[0]交换后,将最后一个元素从堆中排除
44             MinHeapFixDown(dw, 0, i); //将每次交换后-1的堆从dw[0]开始,调整为新的最小堆
45         }
46     }
47     
48     //交换DataWrap数组中i,j两数值
49     public static void swap(DataWrap[] dw,int i,int j)
50     {
51         DataWrap temp;
52         temp = dw[i];
53         dw[i] = dw[j];
54         dw[j] = temp;
55     } 
56     
57     public static void main(String[] args)
58     {
59         DataWrap[] dw = {new DataWrap(2,""),new DataWrap(45,""),new DataWrap(36,""),new DataWrap(8,""),new DataWrap(78,""),new DataWrap(99,"")};
60         System.out.println("待排序数据为:" + Arrays.toString(dw));
61         HeapSort.heapSort(dw);
62         System.out.println("排序后数据为:" + Arrays.toString(dw));
63             
64     }
65 
66 }
View Code

 

二、交换排序

1、冒泡排序

  1.比较相邻的前后二个数据,如果前面数据大于后面的数据,就将二个数据交换。

  2.这样对数组的第0个数据到N-1个数据进行一次遍历后,最大的一个数据就“沉”到数组第N-1个位置。

  3.N=N-1,如果N不为0就重复前面二步,否则排序完成。

经典排序算法(Java实现)
 1 public static void bubbleSort(DataWrap[] dw)
 2     {
 3         int n = dw.length;
 4         boolean flag;//设置标志位,若发生未交换的情况,说明已经有序,退出循环即可
 5         for(int i = n-1;i > 0 ;i--)
 6         {
 7             flag = false;
 8             for(int j = 0;j < i;j++)
 9             {
10                 if(dw[j].compareTo(dw[j+1]) > 0)
11                 {
12                     swap(dw,j+1,j);
13                     flag = true;
14                 }
15             }
16             if(!flag)
17             {
18                 break;
19             }
20             System.out.println("排序中顺序:" + Arrays.toString(dw));
21         }
22     }
View Code

2、快速排序

  快速选择排序主要思路是:

  “挖坑填数+分治法”,首先令i =L; j = R; 将a[i]挖出形成第一个坑,称a[i]为基准数。然后j--由后向前找比基准数小的数,找到后挖出此数填入前一个坑a[i]中,再i++由前

向后找比基准数大的数,找到后也挖出此数填到前一个坑a[j]中。重复进行这种“挖坑填数”直到i==j。再将基准数填入a[i]中,这样i之前的数都比基准数小,i之后的数都比基准数

大。因此将数组分成二部分再分别重复上述步骤就完成了排序。

经典排序算法(Java实现)
 1 public class QuickSort
 2 {
 3     public static void quickSort(DataWrap[] dw,int l,int r)
 4     {
 5         if(l < r)
 6         {
 7             int i,j;
 8             DataWrap mid;
 9             i = l;
10             j = r;
11             mid = dw[i];
12             while(i < j)
13             {
14                 while(i < j && dw[j].compareTo(mid) >= 0)
15                     j--;
16                 if(i < j)
17                     dw[i++] = dw[j];
18                 while(i < j && dw[i].compareTo(mid) <= 0)
19                     i++;
20                 if(i < j)
21                     dw[j--] = dw[i];
22             }
23             dw[i] = mid;  
24             quickSort(dw, l, i-1);  //递归调用
25             quickSort(dw, i+1, r);
26         }
27     }
28     
29     public static void main(String[] args) 
30     {
31         DataWrap[] dw = 
32             {
33                 new DataWrap(9, ""),
34                 new DataWrap(-16, ""),
35                 new DataWrap(21, "*"),
36                 new DataWrap(23, ""),
37                 new DataWrap(-30, ""),
38                 new DataWrap(-49, ""),
39                 new DataWrap(21, ""),
40                 new DataWrap(30, "*"),
41                 new DataWrap(13, "*")
42             };
43         System.out.println("排序前元素:" + Arrays.toString(dw));
44         int n = dw.length;
45         QuickSort.quickSort(dw, 0, n-1);
46         System.out.println("排序后元素:" + Arrays.toString(dw));    
47     }
48 }
View Code

 

三、插入排序

1、直接插入排序

  每次将一个待排序的记录,按其关键字大小插入到前面已经排好序的子序列中的适当位置,直到全部记录插入完成为止。

经典排序算法(Java实现)
 1 public static void directInsertSort(DataWrap[] dw,int n)
 2     {
 3         for(int i = 1;i < n;i++)
 4         {
 5             if(dw[i].compareTo(dw[i-1]) < 0)
 6             {
 7                 DataWrap temp = dw[i];
 8                 int j;
 9                 for(j = i-1;j >= 0 && dw[j].compareTo(temp) > 0;j--)
10                 {
11                     dw[j+1] = dw[j];
12                 }
13                 dw[j+1] = temp;
14             }
15         }
16     }
View Code

2、希尔排序(Shell排序、缩小增量排序)

  先将整个待排元素序列分割成若干个子序列(由相隔某个“增量”的元素组成的)分别进行直接插入排序,然后依次缩减增量再进行排序,待整个序列中的元素基本有

序(增量足够小)时,再对全体元素进行一次直接插入排序。由于希尔排序是对相隔若干距离的数据进行直接插入排序,因此可以形象的称希尔排序为“跳着插

经典排序算法(Java实现)
 1     public static void shellSort(DataWrap[] dw)
 2     {
 3         int n = dw.length;
 4         for(int gap = n/2;gap > 0;gap /= 2)
 5         {
 6             for(int i = 0;i < gap;i++)
 7             {
 8                 for(int j = i + gap;j < n;j +=gap)
 9                 {
10                     if(dw[j-gap].compareTo(dw[j]) > 0)
11                     {
12                         DataWrap temp = dw[j];
13                         int k = j-gap;
14                         while(k >= 0 && dw[k].compareTo(temp) > 0)
15                         {
16                             dw[k+gap] = dw[k];
17                             k -= gap;
18                         }
19                         dw[k+gap] = temp;
20                     }
21                 }
22             }
23         }
24     }
View Code

 

四、归并排序(未完)

 

注:本文主要参考:MoreWindows白话经典算法(http://blog.csdn.net/morewindows/article/details/17488865)

          《疯狂Java程序员的基本修养》

经典排序算法(Java实现),布布扣,bubuko.com

经典排序算法(Java实现)

上一篇:ASP.NET Web API路由系统:路由系统的几个核心类型


下一篇:代码提交 以及代码优化