1 概述
本文对比较常用且比较高效的排序算法进行了总结和解析，并贴出了比较精简的实现代码，包括选择排序、插入排序、归并排序、希尔排序、快速排序等。算法性能比较如下图所示：
2 选择排序
选择排序的第一趟处理是从数据序列所有n个数据中选择一个最小的数据作为有序序列中的第1个元素并将它定位在第一号存储位置，第二趟处理从数据序列的n-1个数据中选择一个第二小的元素作为有序序列中的第2个元素并将它定位在第二号存储位置，依此类推，当第n-1趟处理从数据序列的剩下的2个元素中选择一个较小的元素作为有序序列中的最后第2个元素并将它定位在倒数第二号存储位置，至此，整个的排序处理过程就已完成。
代码如下：
- public class SelectionSort {
- public void selectionSort(int[] array) {
- int temp;
- for (int i = 0; i < array.length - 1; i++) {
- for (int j = i + 1; j <= array.length - 1; j++) {// 第i个和第j个比较j可以取到最后一位，所以要用j<=array.length-1
- if (array[i] > array[j]) {// 注意和冒泡排序的区别，这里是i和j比较。
- temp = array[i];
- array[i] = array[j];
- array[j] = temp;
- }
- }
- // 打印每趟排序结果
- for (int m = 0; m <= array.length - 1; m++) {
- System.out.print(array[m] + "\t");
- }
- System.out.println();
- }
- }
-
- public static void main(String[] args) {
- SelectionSort selectionSort = new SelectionSort();
- int[] array = { 5, 69, 12, 3, 56, 789, 2, 5648, 23 };
- selectionSort.selectionSort(array);
- for (int m = 0; m <= array.length - 1; m++) {
- System.out.print(array[m] + "\t");
- }
- }
- }
复制代码
3 插入排序
直接插入排序法的排序原则是：将一组无序的数字排列成一排，左端第一个数字为已经完成排序的数字，其他数字为未排序的数字。然后从左到右依次将未排序的数字插入到已排序的数字中。
代码如下：
- public class InsertSort {
- public void insertSort(int[] array, int first, int last) {
- int temp, i, j;
- for (i = first + 1; i <= last - 1; i++) {// 默认以第一个数为有序序列，后面的数为要插入的数。
- temp = array[i];
- j = i - 1;
- while (j >= first && array[j] > temp) {// 从后进行搜索如果搜索到的数小于temp则该数后移继续搜索，直到搜索到小于或等于temp的数即可
- array[j + 1] = array[j];
- j--;
- }
- array[j + 1] = temp;
- // 打印每次排序结果
- for (int m = 0; m <= array.length - 1; m++) {
- System.out.print(array[m] + "\t");
- }
- System.out.println();
- }
- }
-
- public static void main(String[] args) {
- InsertSort insertSort = new InsertSort();
- int[] array = { 5, 69, 12, 3, 56, 789, 2, 5648, 23 };
- insertSort.insertSort(array, 0, array.length);// 注意此处是0-9而不是0-8
- for (int i = 0; i <= array.length - 1; i++) {
- System.out.print(array[i] + "\t");
- }
- }
- }
复制代码
4 归并排序
算法描述：
把序列分成元素尽可能相等的两半。
把两半元素分别进行排序。
把两个有序表合并成一个。
代码如下：
- public class MergeSortTest {
- public void sort(int[] array, int left, int right) {
- if (left >= right)
- return;
- // 找出中间索引
- int center = (left + right) / 2;
- // 对左边数组进行递归
- sort(array, left, center);
- // 对右边数组进行递归
- sort(array, center + 1, right);
- // 合并
- merge(array, left, center, right);
- // 打印每次排序结果
- for (int i = 0; i < array.length; i++) {
- System.out.print(array[i] + "\t");
- }
- System.out.println();
-
- }
-
- /**
- * 将两个数组进行归并，归并前面2个数组已有序，归并后依然有序
- *
- * @param array
- * 数组对象
- * @param left
- * 左数组的第一个元素的索引
- * @param center
- * 左数组的最后一个元素的索引，center+1是右数组第一个元素的索引
- * @param right
- * 右数组最后一个元素的索引
- */
- public void merge(int[] array, int left, int center, int right) {
- // 临时数组
- int[] tmpArr = new int[array.length];
- // 右数组第一个元素索引
- int mid = center + 1;
- // third 记录临时数组的索引
- int third = left;
- // 缓存左数组第一个元素的索引
- int tmp = left;
- while (left <= center && mid <= right) {
- // 从两个数组中取出最小的放入临时数组
- if (array[left] <= array[mid]) {
- tmpArr[third++] = array[left++];
- } else {
- tmpArr[third++] = array[mid++];
- }
- }
- // 剩余部分依次放入临时数组（实际上两个while只会执行其中一个）
- while (mid <= right) {
- tmpArr[third++] = array[mid++];
- }
- while (left <= center) {
- tmpArr[third++] = array[left++];
- }
- // 将临时数组中的内容拷贝回原数组中
- // （原left-right范围的内容被复制回原数组）
- while (tmp <= right) {
- array[tmp] = tmpArr[tmp++];
- }
- }
-
- public static void main(String[] args) {
- int[] array = new int[] { 5, 69, 12, 3, 56, 789, 2, 5648, 23 };
- MergeSortTest mergeSortTest = new MergeSortTest();
- mergeSortTest.sort(array, 0, array.length - 1);
- System.out.println("排序后的数组：");
- for (int m = 0; m <= array.length - 1; m++) {
- System.out.print(array[m] + "\t");
- }
- }
- }
复制代码
5 希尔排序
希尔排序又称“缩小增量排序”，该方法的基本思想是：先将整个待排元素序列分割成若干个子序列（由相隔某 个“增量”的元素组成的）分别进行直接插入排序，然后依次缩减增量再进行排序，待整个序列中的元素基本有序（增量足够小）时，再对全体元素进行一次直接插 入排序。因为直接插入排序在元素基本有序的情况下（接近最好情况），效率是很高的，因此希尔排序在时间效率上比前两种方法有较大提高。
代码如下：
- public class ShellSort {
- public void shellSort(int[] array, int n) {
- int i, j, gap;
- int temp;
- for (gap = n / 2; gap > 0; gap /= 2) {// 计算gap大小
- for (i = gap; i < n; i++) {// 将数据进行分组
- for (j = i - gap; j >= 0 && array[j] > array[j + gap]; j -= gap) {// 对每组数据进行插入排序
- temp = array[j];
- array[j] = array[j + gap];
- array[j + gap] = temp;
- }
- // 打印每趟排序结果
- for (int m = 0; m <= array.length - 1; m++) {
- System.out.print(array[m] + "\t");
- }
- System.out.println();
- }
- }
- }
-
- public static void main(String[] args) {
- ShellSort shellSort = new ShellSort();
- int[] array = { 5, 69, 12, 3, 56, 789, 2, 5648, 23 };
- shellSort.shellSort(array, array.length);// 注意为数组的个数
- for (int m = 0; m <= array.length - 1; m++) {
- System.out.print(array[m] + "\t");
- }
- }
- }
复制代码
6 快速排序
快速排序（Quicksort）是对冒泡排序的一种改进。由C. A. R. Hoare在1962年提出。它的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然 后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。
代码如下：
- <font size="3"><pre class="brush: csharp; gutter: false; first-line: 1">public class QuickSort {
- public int partition(int[] sortArray, int low, int height) {
- int key = sortArray[low];// 刚开始以第一个数为标志数据
- while (low < height) {
- while (low < height && sortArray[height] >= key)
- height--;// 从后面开始找，找到比key值小的数为止
- sortArray[low] = sortArray[height];// 将该数放到key值的左边
- while (low < height && sortArray[low] <= key)
- low++;// 从前面开始找，找到比key值大的数为止
- sortArray[height] = sortArray[low];// 将该数放到key值的右边
- }
- sortArray[low] = key;// 把key值填充到low位置，下次重新找key值
- // 打印每次排序结果
- for (int i = 0; i <= sortArray.length - 1; i++) {
- System.out.print(sortArray[i] + "\t");
- }
- System.out.println();
- return low;
- }
-
- public void sort(int[] sortArray, int low, int height) {
- if (low < height) {
- int result = partition(sortArray, low, height);
- sort(sortArray, low, result - 1);
- sort(sortArray, result + 1, height);
- }
- }
-
- public static void main(String[] args) {
- QuickSort quickSort = new QuickSort();
- int[] array = { 5, 69, 12, 3, 56, 789, 2, 5648, 23 };
- for (int i = 0; i <= array.length - 1; i++) {
- System.out.print(array[i] + "\t");
- }
- System.out.println();
- quickSort.sort(array, 0, 8);
- for (int i = 0; i <= array.length - 1; i++) {
- System.out.print(array[i] + "\t");
- }
- }
- }</pre></font><pre class="brush: csharp; gutter: false; first-line: 1"></pre>
复制代码
文章来源：
http://www.mfqyw.com/
