java几种排序法.doc

1 import java.util.Date;
2
3 public class Sort
4 {
5 public static void main(String[] args)
6 {
7 int[] arr = { 10, 32, 1, 9, 5, 7, 12, 0, 4, 3 }; // array
8
9 long time1=new Date().getTime();
10 //insertSort(arr);
11 //selectSort(arr);
12 quickSort(arr,0,arr.length-1);
13 System.out.println(new Date().getTime()-time1);
14 for(int i=0;i<10;i++)
15 {
16 System.out.print(arr[i]+" ");
17 }
18 }
19
20 //插入排序
21 public static void insertSort(int[] arr)
22 {
23
24 for(int j=1;j<arr.length;j++)
25 {
26 int key=arr[j];
27 int i=j-1;
28 while(i>=0&&arr[i]>key)
29 {
30 arr[i+1]=arr[i];
31 i--;
32 }
33 arr[i+1]=key;
34 }
35 }
36 //选择排序
37 public static void selectSort(int[] arr)
38 {
39 for(int i=0;i<arr.length-1;i++)
40 {
41 int minIndex=i;
42 for(int j=i+1;j<arr.length;j++)
43 {
44 if(arr[minIndex]>arr[j])
45 {
46 minIndex=j;
47 }
48 }
49 if(minIndex!=i)
50 {
51 int temp=arr[i];
52 arr[i]=arr[minIndex];
53 arr[minIndex]=temp;
54 }
55 }
56 }
57
58 //快速排序
59 public static int[] quickSort(int[] arr,int left,int right)
60 {
61 int i=left,j=right;
62 int middle,temp;
63 middle=arr[(left+right)/2];
64 do
65 {
66 while(arr[i]<middle&&i<right)
67 {
68 i++;
69 }
70 while(arr[j]>middle&&j>left)
71 {
72 j--;
73 }
74 if(i<=j)
75 {
76 temp=arr[i];
77 arr[i]=arr[j];
78 arr[j]=temp;
79 i++;
80 j--;
81 }
82 }while(i<=j);
83
84 if(left<j)
85 {
86 quickSort(arr,left,j);
87 }
88 if(right>i)
89 {
90 quickSort(arr,i,right);
91 }
92
93 return arr;
94
95 }
96
97 }