資料結構--排序--簡單排序

1 /*插入排序--是基本排序裡面性能比較好的(比較适合基本有序的排序)
 2  *排序的思想：一個序列，前邊是有序的，後邊是無序的，拿出一個元素進行插入到已經有序
 3  *           的部分(這裡就涉及移動的操作)--先找到位置，再移動
 4  *特點：一趟排序下來每個元素的位置可能不是固定的
 5  *時間複雜度：O(N2)
 6  *排序的穩定性：穩定的
 7  *使用場景：資料基本有序的情況下
 8  * */
 9 public class TestInsertSort {
10 
11     public static void main(String[] args) {
12         int[] list1 = {10,8,9,7};
13         insertSort(list1);
14         for(int i = 0; i < list1.length; i++){
15             System.out.print(list1[i] + " ");
16         }
17 
18     }
19     
20     public static void insertSort(int[] list){
21         for(int i = 1; i <list.length; i++){
22             //記錄現在被比較的值
23             int temp = list[i];
24             int j = i;
25             //和前面有序的部分比較找到位置插入【滿足>0和比前面的元素小】
26             while(j > 0 && list[j-1] > temp){
27                 list[j] = list[j-1];//向右邊移動
28                 j--;
29             }
30             list[j] = temp;
31         }
32     }
33 
34 }      

1 /*冒泡排序--屬于簡單排序
 2  *思想：就是每兩個相鄰的元素比較-交換直到排完一趟排序，确定出最大的一個元素
 3  *具體實作：需要嵌套循環 
 4  *外循環：控制排序趟數--n-1
 5  *内循環：控制每趟的比較次數n-1/n-2....
 6  *冒泡排序的時間複雜度：O(N2)--比較+交換
 7  *排序的穩定性：指的是存在相同的值的元素排序後相對位置不變
 8  *本質就是較換的條件是：大于而不是大于等于
 9  * */
10 public class TestBubbleSort {
11 
12     public static void main(String[] args) {
13         int[] list = {10, 8,7,9,2,3,1,0};
14         int[] list1 = bubbleSort(list);
15         for(int i = 0; i < list1.length; i++){
16             System.out.print(list1[i] + " ");
17         }
18     }
19     
20     public static int[] bubbleSort(int[] list){
21         //外部循環控制排序的趟數
22         for(int i = 1; i < list.length; i++){
23             //内部比較每趟比較的次數
24             for(int j = 0; j <list.length - i; j++ ){
25                 if(list[j] > list[j+1]){//保證排序的穩定性
26                     int temp = list[j];
27                     list[j] = list[j+1];
28                     list[j+1] = temp;
29                     
30                 }
31             }
32         }
33         return list;
34     }
35     
36     
37 
38 }      

1 /*選擇排序--對冒泡排序的一定的改進，減少了較好的次數
 2  *基本思路：将第一個元素與後面的所有元素比較，找到最小的元素與第一個交換
 3  *          完成一次排序，後面依次找出第二小等等
 4  *具體實作：嵌套循環(外控制排序趟數，内控制交換次數)
 5  *選擇排序的時間複雜度：O(N2)
 6  *排序的穩定性：穩定
 7  *使用場景：資料量比較小的情況下
 8  * */
 9 public class TestSelectSort {
10 
11     public static void main(String[] args) {
12         int[] list1 = {10,8,0,7,9,7,6,5,4};
13         selectSort(list1);
14         for(int i = 0; i < list1.length; i++){
15             System.out.print(list1[i] + " ");
16         }
17     }
18     
19     //以及有序的不在參與比較【減少較好次數】
20     public static void selectSort(int[] list){
21         for(int i = 0; i < list.length -1; i++){
22             for(int j = i + 1; j < list.length; j++){
23                 if(list[i] > list[j]){
24                     int temp = list[i];
25                     list[i] =list[j];
26                     list[j] = temp;
27                 }
28             }
29         }
30     }
31 
32 }