时间戳

首页 > 技术文章 > 排序算法1——（选择、插入、冒泡）

排序算法1——（选择、插入、冒泡）

Eason-S 2016-05-14 22:59 原文

一.选择排序

算法复杂度：O(n^2) 

原理：对于给定的一组记录，经过第一轮比较后得到最小的记录，然后将该记录的位置与第一个记录的位置进行交换；接着对不包括以第一个记录的其他记录进行第二轮比较，得到最小的记录并与第二个纪录进行位置交换；重复该过程，直到进行比较的记录只有一个为止。

示例程序如下：

 1 public class select {
 2     
 3     public static void selectSort(int[] a){
 4         int temp,flag;
 5         int length = a.length;
 6         for(int i=0;i<length;i++){
 7             temp = a[i];
 8             flag = i;
 9             for(int j=i+1;j<length;j++){
10                 if(a[j]<temp){
11                     temp =a[j];
12                     flag = j;
13                 }
14             }
15             if(flag != i){
16                 a[flag] = a[i];
17                 a[i] = temp;
18             }
19         }    
20     }
21     
22     public static void main(String[] args){
23         int a[] = {5,4,9,8,7,6,0,1,3,2};
24         int len = a.length;
25         selectSort(a);
26         for(int i=0;i<len;i++){
27             System.out.println(a[i]+" ");
28         }
29     }
30 }

二.插入排序

算法复杂度：O(n^2) 

原理：对于给定的一组记录，初始时假设第一个记录自成一个有序序列，其余记录为无序序列。接着从第二个纪录开始，按照记录的大小将当前处理的记录插入到其之前的有序序列中，直至最后一个记录插入到有序序列中为止。

示例程序如下：

 1 public class insert {
 2     public static void insertSort(int[] a){
 3         int j,temp,length = a.length;
 4         if(a != null){
 5             for(int i=1;i<length;i++){
 6                 temp = a[i];
 7                 j = i;
 8                 if(a[j-1]>temp){
 9                     while(j>=1&&a[j-1]>temp){
10                         a[j] = a[j-1];
11                         j--;
12                     }
13                 }
14                 a[j] = temp;
15             }
16         }
17     }
18     
19     public static void main(String[] args){
20         int a[] = {5,4,9,8,7,6,0,1,3,2};
21         int len = a.length;
22         insertSort(a);
23         for(int i=0;i<len;i++){
24             System.out.println(a[i]+" ");
25         }
26     }
27 }

三.冒泡排序

算法复杂度：O(n^2) 

原理：对于给定的n个记录，从第一个记录开始依次对相邻的两个记录进行比较，当前面的记录大于后面的记录时，交换位置，进行一轮比较和换位后，n个记录中的最大记录将位于第n位，然后对前（n-1）个记录进行第二轮比较；重复该过程直到进行比较的记录只剩下一个为止。

示例程序如下：

 1 public class bubble {
 2     public static void bubbleSort(int[] a){
 3         int temp,length = a.length;
 4         for(int i=0;i<length-1;i++){
 5             for(int j=length-1;j>i;j--){
 6                 if(a[j]<a[j-1]){
 7                     temp = a[j];
 8                     a[j] = a[j-1];
 9                     a[j-1] = temp;
10                 }
11             }
12         }
13     }
14     
15     public static void main(String[] args){
16         int a[] = {5,4,9,8,7,6,0,1,3,2};
17         int len = a.length;
18         bubbleSort(a);
19         for(int i=0;i<len;i++){
20             System.out.println(a[i]+" ");
21         }
22     }
23 }

冒泡排序优化：

当给定的待排序的记录中除少量关键字需要交换外，其他关键字均为正常顺序时，进行了大量多余比较（如{2,1,3,4,5,6,7,8,9}）。我们可以通过增加一个标记变量flag来实现改进。

 1 public static void bubbleSort(int[] a){
 2         int temp,length = a.length;
 3         boolean flag = true;                    //flag用来作为标记
 4         for(int i=0;i<length-1 && flag;i++){    //若flag为true则退出循环
 5             flag = false;                        //初始设为false
 6             for(int j=length-1;j>i;j--){
 7                 if(a[j]<a[j-1]){
 8                     temp = a[j];
 9                     a[j] = a[j-1];
10                     a[j-1] = temp;
11                     flag = true;                //如果有数据交换，则flag为true
12                 }
13             }
14             if (flag == true) 
15                 break;
16         }
17 }

 

推荐阅读