常用的排序算法

发表于 | 分类于 | | 阅读次数

logo

日常操作中常见的排序方法有：冒泡排序、快速排序、选择排序、插入排序、希尔排序，甚至还有基数排序、鸡尾酒排序、桶排序、鸽巢排序、归并排序等。

下面一一列举

一、冒泡排序

原理是临近的数字两两进行比较,按照从小到大或者从大到小的顺序进行交换,

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
  /**  
 * 冒泡法排序<br/>  
 * <li>比较相邻的元素。如果第一个比第二个大，就交换他们两个。</li>  
 * <li>对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。</li>  
 * <li>针对所有的元素重复以上的步骤，除了最后一个。</li>  
 * <li>持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。</li>  
 *   
 * @param arr  
 * 需要排序的整型数组  
 */  
public static void bubbleSort(int[] arr){
	for(int i=0; i<arr.length-1; i++){
		for(int j=i+1; j<arr.length; j++){
			if(arr[i] > arr[j]){
				int temp = arr[i];
				arr[i] = arr[j];
				arr[j] = temp;
			}
		}
	}
	System.out.println(Arrays.toString(arr));
}
 public static void main(String[] args) {
	int[] arr = {1,3,5,2,4};
    bubbleSort(arr);
}

结果 [1,2,3,4,5]

====================================================

选择排序

简单选择排序的基本思想：给定数组：int[] arr={里面n个数据}；第1趟排序，在待排序数据arr[1]~arr[n]中选出最小的数据，将它与arrr[1]交换；第2趟，在待排序数据arr[2]~arr[n]中选出最小的数据，将它与r[2]交换;以此类推，第i趟在待排序数据arr[i]~arr[n]中选出最小的数据，将它与r[i]交换，直到全部排序完成。

代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public static void selectSort(int[] arr){
    	for(int i=0; i<arr.length; i++){
    		int min = arr[i];
    		int index = 0;
    		for(int j=i; j<arr.length; j++){
    			if(arr[j] <= min){
    			    min = arr[j];
    				index = j;
    			}
    		}
    		int temp = arr[index];
    		arr[index] = arr[i];
    		arr[i] = temp;
    	}
    	System.out.println(Arrays.toString(arr));
    }
	public static void main(String[] args) {
		int[] arr = {1,1,3,5,2};
	    selectSort(arr);
	}

结果:[1, 1, 2, 3, 5]

=======================================================

插入排序

通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应的位置并插入。

代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
// 插入排序
  public static void insertSort(int[] arr){
     for(int i=1; i<arr.length; i++){
       int temp = arr[i];       
         while(i>0 && temp<arr[i-1]){
          arr[i] = arr[i-1];
          i--;
         }
         arr[i] = temp;
     }
     System.out.println(Arrays.toString(arr));
  }
public static void main(String[] args) {
  int[] arr = {2,1,4,7,0,2,343,123,12,11,1};
    insertSort(arr);
}

结果:[0, 1, 1, 2, 2, 4, 7, 11, 12, 123, 343]

==============================================================

快速排序

快速排序原理是分治思想，是冒泡排序的改进型。首先选择一个基准数,然后先从数组后端开始，如果发现有元素比该基准点的值小，就交换lo和hi位置的值，然后从前半部分开始扫描，发现有元素大于基准点的值，就交换lo和hi位置的值，如此往复循环，直到lo>=hi,然后把基准点的值放到hi这个位置。一次排序就完成了。以后采用递归的方式分别对前半部分和后半部分排序，当前半部分和后半部分均有序时该数组就自然有序了。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
//快速排序
   public static int partition(int []array,int lo,int hi){
       //固定的切分方式
       int key=array[lo];
       while(lo<hi){
           while(array[hi]>=key&&hi>lo){//从后半部分向前扫描
               hi--;
           }
           array[lo]=array[hi];
           while(array[lo]<=key&&hi>lo){//从前半部分向后扫描
               lo++;
           }
           array[hi]=array[lo];
       }
       array[hi]=key;
       return hi;
   }
   public static void sort(int[] array,int lo ,int hi){
       if(lo>=hi){
           return ;
       }
       int index=partition(array,lo,hi);
       sort(array,lo,index-1);
       sort(array,index+1,hi);
   }
 public static void main(String[] args) {
   int[] arr = {2,1,4,7,0,2,343,123,12,11,1};
     sort(arr,0,arr.length-1);
     System.out.println(Arrays.toString(arr));
 }

结果: [0, 1, 1, 2, 2, 4, 7, 11, 12, 123, 343]

===========================================================