各种排序

  1 package com.hw.sorts0512;
  2 
  3 public class AllKindsOfSorts {
  4     private int pivot,index;
  5     private int gap;
  6     private boolean change,flag;
  7     
  8     public void bubbleSort(int[] arr){  //冒泡排序
  9         for(int i = arr.length - 1;i>=0;i--){
 10             flag = false;
 11             for(int j = 0;j < i;j++){
 12                 if(arr[j] > arr[j+1]){
 13                     int temp = arr[j];
 14                     arr[j] = arr[j+1];
 15                     arr[j+1] = temp;
 16                     flag = true;
 17                 }
 18             }
 19             if(flag == false){
 20                 break;
 21             }
 22         }
 23     }
 24     
 25     private int partition(int[] arr,int low,int high)  //快速排序分割方法
 26     {
 27         pivot = arr[low];
 28         while(low < high)
 29         {
 30             while(low<high && pivot<=arr[high])
 31             {
 32                 high--;
 33             }
 34             arr[low] = arr[high];
 35             
 36             while(low<high && pivot>=arr[low])
 37             {
 38                 low++;
 39             }
 40             arr[high] = arr[low];
 41         }
 42         arr[low] = pivot;
 43         return low;
 44     }
 45     
 46     public void quickSort(int[] arr,int low,int high)  //快速排序
 47     {
 48         if(low < high){
 49             index = partition(arr,low,high);
 50             quickSort(arr,low,index-1);
 51             quickSort(arr,index+1,high);
 52         }
 53     }
 54     
 55     public void insertSort(int[] arr){  //插入排序
 56         for(int i = 1;i < arr.length;i++){
 57             int j = i;
 58             while(j > 0 && arr[j] < arr[j-1])
 59             {
 60                 int temp = arr[j];
 61                 arr[j] = arr[j-1];
 62                 arr[j-1] = temp;
 63                 j--;
 64             }
 65         }
 66     }
 67     
 68     public void shellSort(int[] arr){  //希尔排序
 69         for(gap = arr.length/2;gap > 0;gap /= 2){
 70             for(int i = gap;i < arr.length;i++){
 71                 int j = i;
 72                 while(j-gap >= 0 && arr[j] < arr[j-gap])
 73                 {
 74                     int temp = arr[j];
 75                     arr[j] = arr[j-1];
 76                     arr[j-1] = temp;
 77                     j -= gap;
 78                 }
 79             }
 80         }
 81     }
 82     
 83     public void mergeSort(int[] arr){  //归并排序
 84         int[] temp = new int[arr.length];
 85         divide(arr,0,arr.length-1,temp);
 86     }
 87     
 88     private void divide(int[] arr,int left,int right,int[] temp){
 89         if(left < right){  //递归结束条件
 90             int mid = (left + right) / 2;  //取arr数组的中间值
 91             divide(arr,left,mid,temp);
 92             divide(arr,mid+1,right,temp);
 93             merge(arr,left,mid,right,temp);
 94         }
 95     }
 96     
 97     private void merge(int[] arr,int left,int mid,int right,int[] temp){  //把分割的数一个一个合并
 98         int pLeft = left,pRight = mid+1,pTemp = 0;
 99         while(pLeft<=mid && pRight<=right)
100         {
101             if(arr[pLeft] <= arr[pRight]){
102                 temp[pTemp++] = arr[pLeft++];
103             }else{
104                 temp[pTemp++] = arr[pRight++];
105             }
106         }
107         while(pLeft <= mid)
108         {
109             temp[pTemp++] = arr[pLeft++];
110         }
111         while(pRight <= right)
112         {
113             temp[pTemp++] = arr[pRight++];
114         }
115         
116         pTemp = 0;
117         while(left <= right)
118         {
119             arr[left++] = temp[pTemp++];
120         }
121     }
122     
123     public void selectSort(int[] arr){  //选择排序
124         for(int i = 0;i < arr.length - 1;i++){
125             int index = i;
126             for(int j = i + 1;j < arr.length;j++){
127                 if(arr[j] < arr[index]){
128                     index = j;
129                     change = true;
130                 }
131             }
132             if(change == true){
133                 int temp = arr[index];
134                 arr[index] = arr[i];
135                 arr[i] = temp;
136             }
137         }
138     }
139     
140     private void createHeap(int[] arr,int i,int length){  //堆排序
141         int temp = arr[i];  //A
142         for(int k = i*2 + 1;k<length;k=k*2+1){  //从当前结点的叶子结点开始
143             if(k+1<length && arr[k]<arr[k+1]){  //这一步是找出当前结点的左右孩子结点中比较大的那一个
144                 k++;
145             }
146             
147             if(arr[k] > temp){   //孩子比父亲大，就得交换
148                 arr[i] = arr[k];  //B
149                 i = k;  //C  //这一步交换如果看不懂模拟程序运行，一下就懂了
150             }else{
151                 break;
152             }
153         }
154         arr[i] = temp;  //D
155     }
156      //以上A,B,C,D四步就是交换两个元素的过程
157     private void swap(int[] arr,int a,int b){
158         int temp = arr[a];
159         arr[a] = arr[b];
160         arr[b] = temp;
161     }
162     
163     public void heapSort(int[] arr){
164         for(int i = arr.length/2-1;i>=0;i--){
165             createHeap(arr,i,arr.length);
166         }
167         
168         for(int j = arr.length-1;j>0;j--){
169             swap(arr,0,j);
170             createHeap(arr,0,j);
171         }
172     }
173 }

 1 package com.hw.sorts0512;
 2 
 3 import java.util.Scanner;
 4 
 5 public class BubbleSort {
 6     private void run(){
 7         int len;
 8         int[] data = null;
 9         AllKindsOfSorts th = new AllKindsOfSorts();
10         Scanner s = new Scanner(System.in);
11         System.out.println("请输入数组长度：");
12         len = s.nextInt();
13         data = new int[len];
14         System.out.println("请输入数组中的元素：");
15         for(int i = 0;i < len;i++){
16             data[i] = s.nextInt();
17         }
18         th.bubbleSort(data);
19         System.out.println("采用冒泡排序后的数组是：");
20         for(int i = 0;i < len;i++){
21             System.out.print(data[i]+" ");
22         }
23     }
24     
25     public static void main(String[] args){
26         BubbleSort bs = new BubbleSort();
27         bs.run();
28     }
29 }