八大排序简单总结

 1 for(int i=1 ; i){
 2                 //将刚进来的数交给temp
 3             int temp=a[i];                                                
 4             int j;
 5                 //从后面开始排序将数较小的往前移动
 6             for ( j = i; j > 0&&temp) {                        
 7                 a[j]=a[j-1];
 8             }
 9                 //将新新进来的数插入到不能移动的位置
10             a[j]=temp;                            
11         }

 1 /*
 2          * 第一层循环主要是控制分组的情况，通俗的话说就是控制间隔数
 3          * 第二层循环保证了在其实为d的时候后面所有的数据都能够比较，所有的元素都是从后面开始向前面比较
 4          * 第三层循环主要是交换数据
 5          */
 6         for (int d = a.length/2; d > 0 ; d=d/2) {
 7             for (int i = d; i ) {
 8                 int temp=a[i];
 9                 int j;
10                 //j >= d  保证j位于d到a.length之间，并且循环的时候每次减少的是d而不是1
11                 for ( j = i; j >= d&&temp d) {
12                     a[j]=a[j-d];
13                 }
14                 a[j]=temp;
15             }
16         }

 1 package com.hone.Shell;
 2 
 3 public class TestShell {
 4     public static void main(String[] args) {
 5         int a[]={2,1,7,6,89,34,45,23,24,88};
 6         System.out.print("排序之前： ");
 7         for (int i = 0; i ) {
 8             System.out.print(a[i]+" ");
 9         }
10         System.out.println();
11         /*
12          * 第一层循环主要是控制分组的情况，通俗的话说就是控制间隔数
13          * 第二层循环保证了在其实为d的时候后面所有的数据都能够比较
14          * 第三层循环主要是交换数据
15          */
16         for (int d = a.length/2; d > 0 ; d=d/2) {
17             for (int i = d; i ) {
18                 int temp=a[i];
19                 int j;
20                 //j >= d  保证j不会出界，并且循环的时候每次减少的是d而不是1
21                 for ( j = i; j >= d&&temp d) {
22                     a[j]=a[j-d];
23                 }
24                 a[j]=temp;
25             }
26         }
27         
28         System.out.print("排序之后： ");
29         for (int i = 0; i ) {
30             System.out.print(a[i]+" ");
31         }
32     }
33 }

 1 /*
 2          * 选择排序中从数据元素集合中找出最小值，并且将该值与第一个数相交换，
 3          * 然后再从除了第一个数之外的数中找出最小值，并且与第二个数相交换。
 4          * 依次类推直到，所有的数据都交换完毕。
 5          * 选择排序和冒泡排序是逆着进行的，选择排序首先是将最小的元素先排到最前面(并且不具有稳定性)，冒泡排序是将最大的元素先排到末端
 6          */
 7         int temp;
 8         for (int i = 0; i ) {
 9             //假设最小数的都是每次循环的第一个数
10             int min=i;        
11             //找出除了第i个元素之外的其他元素中的最小值
12             for (int j = i+1; j ) {
13                 if (a[j]j;
14             }
15             if (min!=i) {
16                 temp=a[i];
17                 a[i]=a[min];
18                 a[min]=temp;
19             }
20         }

 1 package com.hone.Select;
 2 
 3 public class TestSelectForSteable {
 4     public static void main(String[] args) {
 5         int a[]={2,1,7,6,89,34,45,23,24,88};
 6         System.out.print("排序之前： ");
 7         for (int i = 0; i ) {
 8             System.out.print(a[i]+" ");
 9         }
10         System.out.println();
11         
12         /*
13          * 选择排序中从数据元素集合中找出最小值，并且将该值与第一个数相交换，
14          * 然后再从除了第一个数之外的数中找出最小值，并且与第二个数相交换。
15          * 依次类推直到，所有的数据都交换完毕。
16          * 选择排序和冒泡排序是逆着进行的，选择排序首先是将最小的元素先排到最前面(并且不具有稳定性)，
17          * 冒泡排序是将最大的元素先排到末端
18          * 
19          * 简单的选择排序不稳定，因为有可能将相同的两个数的位置发生了变换
20          * 因此可以在选择出来了最小数，将所有的元素往后移动，然后再将最小数插入到有序数组中
21          * 
22          */
23         int temp;
24         for (int i = 0; i ) {
25             //假设最小数的都是每次循环的第一个数
26             int min=i;        
27             //找出除了第i个元素之外的其他元素中的最小值
28             for (int j = i+1; j ) {
29                 if (a[j]j;
30             }
31             if (min!=i) {
32                 temp=a[min];            //将最小数放入到一个空值中，预留一个空位置
33                 for (int j = min; j > i; j--) {
34                     a[j]=a[j-1];
35                 }
36                 a[i]=temp;                //将最小数插入到已经排好的数组后面
37             }
38         }
39         
40         
41         System.out.print("排序之后： ");
42         for (int i = 0; i ) {
43             System.out.print(a[i]+" ");
44         }
45     }
46 }

 1 package com.hone.Select;
 2 
 3 public class HeapSort {
 4     /*
 5      * 定义一个方法用于创建最大堆
 6      */
 7     public static void createHeap(int[] a, int n,int h){
 8         int i,j,flag;
 9         int temp;
10         
11         i=h;                    //i为要建堆的二叉树根结点下标
12         j= 2 * i+ 1;            //j为i结点的左孩子结点的下标
13         temp=a[i];
14         flag=0;
15         
16         //沿着左右子树中值较大的重复向下删选
17         //当 j 小于叶子节点的时候，并且该结点没有被访问过
18         while(j ){
19             //寻找左右结点的较大者，j为其下标
20             if(j]){
21                 j++;
22             }
23             if (temp>a[j]) flag=1;
24             else {
25                 a[i]=a[j];                //先将叶子结点的值赋给根节点
26                 i=j;
27                 j=2*i+1;                //将j结点一直往下移动
28             }
29         }
30         //将最初的结点a[i]复制给最后的a[j]
31         a[i]=temp;
32     }
33     
34     //初始化最大堆,使每一个子树为最大堆，也就是解决第一个问题
35     public static void initCreateHeap(int[] a){
36         int n=a.length;
37         for (int i = (n-1)/2 ; i >= 0; i--) {
38             createHeap(a, n, i);
39         }
40     }
41     
42     
43     public static void heapSort(int[] a){
44         int temp;
45         int n = a.length;
46         
47         initCreateHeap(a);
48         
49         //当前最大堆个数每次减一,并且将a[0]和当前最大堆的最后一个元素相交换
50         for (int i = n-1; i > 0; i--) {
51             temp=a[0];
52             a[0]=a[i];
53             a[i]=temp;
54             
55             createHeap(a, i, 0);
56         }
57     }
58     
59     public static void main(String[] args) {
60         int a[]={2,1,7,6,89,34,45,23,24,88};
61         System.out.print("排序之前： ");
62         for (int i = 0; i ) {
63             System.out.print(a[i]+" ");
64         }
65         System.out.println();
66         
67         heapSort(a);
68         
69         System.out.print("排序之后： ");
70         for (int i = 0; i ) {
71             System.out.print(a[i]+" ");
72         }
73     }
74     
75 }

 1 /*
 2          * 冒泡排序的思路：首先对相邻的两个数进行比较，第一轮可以将数组中最大的树排到数组的末端
 3          */
 4         for (int i = a.length-1; i >= 0; i--) {        //最多做n-1次排序
 5             int flag=0;
 6             for (int j = 0; j ) {
 7                 if(a[j]>a[j+1]){
 8                     m=a[j];
 9                     a[j]=a[j+1];
10                     a[j+1]=m;
11                     flag=1;
12                 }
13             }
14             //如果没有做任何的交换则直接退出循环，代表原来数组本来就排序
15             if (flag==0)             
16                 break;
17         }

 1 /*
 2  * 快速排序类似于建立哨兵的方式，现在数组中随便定一个 “ 哨 兵  ”，将比哨兵小的数排列在左边
 3  * 将比哨兵大的元素排序在数组的右边，然后在分别对左边，右边的数组利用相同的方法
 4  */
 5 public class QuickSort {
 6     public static void quickSort(int[] a, int low,int high){
 7         int i,j;
 8         int temp;
 9         
10         i=low;
11         j=high;
12         temp=a[low];                //取第一个元素为标准数据元素
13         //下面的对左边和右边的扫描定位反复进行，直到左边的下标i大于或者等于右边元素的下标为止
14         while(i<j){
15             //在数组的右边扫描,如果数大于哨兵，则不改变位置,否则将j上的元素马上移动到i位置，
16             //并且马上扫描左边
17             while( i =temp) j--;
18             if (i<j) {
19                 a[i]=a[j];
20                 i++;
21             }
22             
23             
24             //在数组的左边扫描,如果数小于哨兵，则不改变位置，否则将左边i处的位置交换到
25             //右边j处的位置，并且转回扫描右边
26             while( i ;
27             if (i<j) {
28                 a[j]=a[i];
29                 j--;
30             }
31         }
32         
33         a[i]=temp;
34         
35         //对左边的子集合做递归查询
36         if (low<i) {
37             quickSort(a, low, i-1);
38         }
39         //对右边的子集合做递归查询
40         if (i<high) {
41             quickSort(a, j+1, high);
42         }
43     }

 1 package com.hone.Merge;
 2 
 3 public class MergeSort {
 4     /*
 5      * 定义一个函数包含三个参数，第一个参数表示传入的数组a，第二个参数表示临时储存的数组s
 6      * k，表示当前需要合并的数组的原始长度
 7      */
 8     public static void merge(int[] a ,int[] swap,int k){
 9         int n=a.length;
10         int m=0;
11         int i,j;
12         int s1,s2,e1,e2;            //变量分别表示两个数组的收尾坐标
13         
14         /*
15          * 定义两个数组坐标间的关系
16          */
17         s1=0;
18         while(s1+k <= n-1){
19             s2=s1+k;
20             e1=s2-1;
21             e2=(s2+k-1 <= n-1)?s2+k-1:n-1;            
22             
23         for ( i = s1,j=s2; i <=e1 && j<= e2 ; m++) {
24             if (a[i]<=a[j]) {
25                 swap[m]=a[i];
26                 i++;
27             }else {
28                 swap[m]=a[j];
29                 j++;
30             }
31          }
32         
33         //如果出现了数组2中元素已经归并完毕，数组1仍然未归并完毕,直接将剩下的所有元素直接
34         //赋值给swap
35         while(i<=e1){
36             swap[m]=a[i];
37             i++;
38             m++;
39         }
40         
41         //如果出现了数组1中元素已经归并完毕，数组2仍然未归并完毕，直接将剩下的所有元素直接
42         //赋值给swap
43         while(j<=e2){
44             swap[m]=a[j];
45             j++;
46             m++;
47         }
48         s1=e2+1;                //形成收尾连接
49         }
50         
51         //如果某些集合不能划分为两个数组，则直接全部复制给swap
52         for(i=s1; i)
53             swap[m]=a[i];
54         
55     }
56     
57     //此时定义一个函数主要目的是为了提供合适的函数接口
58     public static void mergeSort(int[] a){
59         int i;
60         int n=a.length;
61         int k=1;
62         int[] swap=new int[n];
63         
64         while(k < n){
65             merge(a, swap, k);
66             
67         
68         for(i=0;i)
69             a[i]=swap[i];
70         
71         k=2 * k;
72         }
73     }
74     
75     public static void main(String[] args) {
76         
77         int a[]={1,7,2,67,89,34,45,23,24,88};
78         
79         System.out.print("排序之前： ");
80         for (int i = 0; i ) {
81             System.out.print(a[i]+" ");
82         }
83         System.out.println();
84         
85         mergeSort(a);
86         
87         System.out.print("排序之后： ");
88         for (int i = 0; i ) {
89             System.out.print(a[i]+" ");
90         }
91     }
92 }