Java排序算法（一）

 1 public class Sort
 2 {
 3     //实现从小到大排序
 4     public static void main(String[] args)
 5     {
 6         int[] arr1 = {9,1,5,8,3,7,4,6,2};
 7         bubbleSort2(arr1);
 8         //selectSort(arr1);
 9         for(int i=0;i<arr1.length;i++)
10         {
11             System.out.println(arr1[i]);
12         }
13     }
14     /*
15     *冒泡排序,相邻两个元素进行比较，如果满足条件进行位置置换
16     *原理：本函数内循环一次，将最值提到冒泡到最尾部
17     *备注：各位大雕可以写一个冒泡到数组头部的，我写冒泡到尾部代码看起来比较好记，哈哈
18     *时间复杂度：比较1+2+3+...+n=n*(n+1)/2次，并做等数量级的记录移动O(n*n)
19     */
20     public static void bubbleSort1(int[] arr)
21     {
22     
23         for(int i=0;i<arr.length-1;i++)
24         {
25             for(int j=0;j<arr.length-1-i;j++)
26             {
27                 if(arr[j]>arr[j+1])
28                 {
29                     int temp = arr[j];
30                     arr[j] = arr[j+1];
31                     arr[j+1] = temp;
32                 }
33             }
34         }
35     }
36     /*
37     *简单选择排序，以一个角标的元素和其他元素进行比较
38     *原理，从n-1-i个记录中选出关键字最小的记录，并和第i个记录交换
39     *时间复杂度：O(n*n)，相对而言，简单选择排序的性能要略优于冒泡排序
40     */
41     public static void selectSort(int[] arr)
42     {
43         for(int i=0;i<arr.length-1;i++)
44         {
45             int min = i;        //将当前下标定义为最小值下标
46             for(int j=i+1;j<arr.length;j++)
47             {
48                 //j初始化为i，表示每次都是数组arr下标为i的元素和后面（i+1）的元素进行比较
49                 if(arr[min]>arr[j])
50                 {
51                     min = j;    //如果有小于当前最小值的关键字，此关键字下标赋值给min
52                 }
53             }
54             if(i!=min)            //如果min不等于i，说明找到最小值，交换
55             {
56                 int temp = arr[i];
57                 arr[i] = arr[min];
58                 arr[min] = temp;
59             }
60         }
61     }
62     /*
63     *直接插入排序，
64     *原理：将一个记录插入到已经排好序的有序表中，从而得到一个新的。记录数增加1的有序表
65     *例子：《大话数据结构》中将其比作抽扑克牌，抽一张排序一张，好书推荐。。。
66     */
67     public static void insertSort(int[] arr)
68     {
69         for(int i=1;i<arr.length;i++)
70         {
71             int temp = arr[i];
72             for(int j=i;j>0&&temp<arr[j-1];j--)
73             {
74 　　　　　　　　　　arr[j]=arr[j-1];
75             }
76　　　　　　　　arr[j]=temp;　　　　　　　　　　
77         }
78     }
79     
80 }