常用排序算法总结

 概述

在计算器科学与数学中，一个排序算法(英语：Sorting algorithm)是一种能将一串数据依照特定排序方式进行排列的一种算法。本文将总结几类常用的排序算法，包括冒泡排序、选择排序、插入排序、快速排序和归并排序，分别使用Java代码实现，简要使用图例方式介绍其实现原理。

算法原理及实现

1、冒泡排序

• 原理图

• 理解

通过重复地遍历要排序的列表，比较每对相邻的项目，并在顺序错误的情况下交换它们。

• Java Code

1. public class BubbleSort { 
2.  
3.     // logic to sort the elements 
4.     public static void bubble_srt(int array[]) { 
5.         int n = array.length; 
6.         int k; 
7.         for (int m = n; m >= 0; m--) { 
8.             for (int i = 0; i < n - 1; i++) { 
9.                 k = i + 1; 
10.                 if (array[i] > array[k]) { 
11.                     swapNumbers(i, k, array); 
12.                 } 
13.             } 
14.             printNumbers(array); 
15.         } 
16.     } 
17.  
18.     private static void swapNumbers(int i, int j, int[] array) { 
19.  
20.         int temp; 
21.         temp = array[i]; 
22.         array[i] = array[j]; 
23.         array[j] = temp; 
24.     } 
25.  
26.     private static void printNumbers(int[] input) { 
27.  
28.         for (int i = 0; i < input.length; i++) { 
29.             System.out.print(input[i] + ", "); 
30.         } 
31.         System.out.println("\n"); 
32.     } 
33.  
34.     public static void main(String[] args) { 
35.         int[] input = { 4, 2, 9, 6, 23, 12, 34, 0, 1 }; 
36.         bubble_srt(input); 
37.     } 
38. } 

2、选择排序

• 原理图

• 理解

内部循环查找下一个最小(或最大)值，外部循环将该值放入其适当的位置。

• Java Code

1. public class SelectionSort { 
2.  
3.     public static int[] doSelectionSort(int[] arr){ 
4.  
5.         for (int i = 0; i < arr.length - 1; i++) 
6.         { 
7.             int index = i; 
8.             for (int j = i + 1; j < arr.length; j++) 
9.                 if (arr[j] < arr[index])  
10.                     index = j; 
11.  
12.             int smallerNumber = arr[index];   
13.             arr[index] = arr[i]; 
14.             arr[i] = smallerNumber; 
15.         } 
16.         return arr; 
17.     } 
18.  
19.     public static void main(String a[]){ 
20.  
21.         int[] arr1 = {10,34,2,56,7,67,88,42}; 
22.         int[] arr2 = doSelectionSort(arr1); 
23.         for(int i:arr2){ 
24.             System.out.print(i); 
25.             System.out.print(", "); 
26.         } 
27.     } 
28. } 

冒泡排序和选择排序的区别

1、冒泡排序是比较相邻位置的两个数，而选择排序是按顺序比较，找最大值或者最小值;

2、冒泡排序每一轮比较后，位置不对都需要换位置，选择排序每一轮比较都只需要换一次位置;

3、冒泡排序是通过数去找位置，选择排序是给定位置去找数。

3、插入排序

• 原理图

• 理解

每一步将一个待排序的记录，插入到前面已经排好序的有序序列中去，直到插完所有元素为止。

• Java Code

1. public class InsertionSort { 
2.  
3. public static void main(String a[]){ 
4.  
5. int[] arr1 = {10,34,2,56,7,67,88,42}; 
6.  
7. int[] arr2 = doInsertionSort(arr1); 
8.  
9. for(int i:arr2){ 
10.  
11. System.out.print(i); 
12.  
13. System.out.print(", "); 
14.  
15. } 
16.  
17. } 
18.  
19. public static int[] doInsertionSort(int[] input){ 
20.  
21. int temp; 
22.  
23. for (int i = 1; i < input.length; i++) { 
24.  
25. for(int j = i ; j > 0 ; j--){ 
26.  
27. if(input[j] < input[j-1]){ 
28.  
29. temp = input[j]; 
30.  
31. input[j] = input[j-1]; 
32.  
33. input[j-1] = temp; 
34.  
35. } 
36.  
37. } 
38.  
39. } 
40.  
41. return input; 
42.  
43. } 
44.  
45. } 

4、快速排序

• 原理图

• 理解

将原问题分解为若干个规模更小，但结构与原问题相似的子问题，递归地解这些子问题，然后将这些子问题的解组合为原问题的解。

1. public class QuickSort { 
2.  
3.     private int array[]; 
4.     private int length; 
5.  
6.     public void sort(int[] inputArr) { 
7.  
8.         if (inputArr == null || inputArr.length == 0) { 
9.             return; 
10.         } 
11.         this.array = inputArr; 
12.         length = inputArr.length; 
13.         quickSort(0, length - 1); 
14.     } 
15.  
16.     private void quickSort(int lowerIndex, int higherIndex) { 
17.  
18.         int i = lowerIndex; 
19.         int j = higherIndex; 
20.         // calculate pivot number, I am taking pivot as middle index number 
21.         int pivot = array[lowerIndex+(higherIndex-lowerIndex)/2]; 
22.         // Divide into two arrays 
23.         while (i <= j) { 
24.             /** 
25.              * In each iteration, we will identify a number from left side which  
26.              * is greater then the pivot value, and also we will identify a number  
27.              * from right side which is less then the pivot value. Once the search  
28.              * is done, then we exchange both numbers. 
29.              */ 
30.             while (array[i] < pivot) { 
31.                 i++; 
32.             } 
33.             while (array[j] > pivot) { 
34.                 j--; 
35.             } 
36.             if (i <= j) { 
37.                 exchangeNumbers(i, j); 
38.                 //move index to next position on both sides 
39.                 i++; 
40.                 j--; 
41.             } 
42.         } 
43.         // call quickSort() method recursively 
44.         if (lowerIndex < j) 
45.             quickSort(lowerIndex, j); 
46.         if (i < higherIndex) 
47.             quickSort(i, higherIndex); 
48.     } 
49.  
50.     private void exchangeNumbers(int i, int j) { 
51.         int temp = array[i]; 
52.         array[i] = array[j]; 
53.         array[j] = temp; 
54.     } 
55.  
56.     public static void main(String a[]){ 
57.  
58.         MyQuickSort sorter = new MyQuickSort(); 
59.         int[] input = {24,2,45,20,56,75,2,56,99,53,12}; 
60.         sorter.sort(input); 
61.         for(int i:input){ 
62.             System.out.print(i); 
63.             System.out.print(" "); 
64.         } 
65.     } 
66. } 

5、归并排序

• 原理图

• 理解

将待排序的数列分成若干个长度为1的子数列，然后将这些数列两两合并;得到若干个长度为2的有序数列，再将这些数列两两合并;得到若干个长度为4的有序数列，再将它们两两合并;直接合并成一个数列为止。

• Java Code