排序算法

发表回复


Java面试宝典系列之基础排序算法




本文就是介绍一些常见的排序算法。排序是一个非常常见的应用场景，很多时候，我们需要根据自己需要排序的数据类型，来自定义排序算法，但是，在这里，我们只介绍这些基础排序算法，包括：插入排序、选择排序、冒泡排序、快速排序（重点）、堆排序、归并排序等等。看下图：

给定数组：int data[] = {9,2,7,19,100,97,63,208,55,78}

一、直接插入排序(内部排序、O(n2)、稳定)

原理：从待排序的数中选出一个来，插入到前面的合适位置。

[java] view plain copy
 在CODE上查看代码片派生到我的代码片
  1. package com.xtfggef.algo.sort;  
  2.   
  3. public class InsertSort {  
  4.   
  5.     static int data[] = { 9, 2, 7, 19, 100, 97, 63, 208, 55, 78 };  
  6.   
  7.     public static void insertSort() {  
  8.         int tmp, j = 0;  
  9.         for (int k = 0; k < data.length; k++) {//-----1-----  
  10.             tmp = data[k];  
  11.             j = k - 1;  
  12.             while (j >= 0 && tmp < data[j]) {//-----2-----  
  13.                 data[j + 1] = data[j];  
  14.                 j--;  
  15.             }  
  16.             data[j + 1] = tmp;//------3-------  
  17.         }  
  18.     }  
  19.   
  20.     public static void main(String[] args) {  
  21.         print();  
  22.         System.out.println();  
  23.         insertSort();  
  24.         System.out.println();  
  25.         print();  
  26.     }  
  27.   
  28.     static void print() {  
  29.         for (int i = 0; i < data.length; i++) {  
  30.             System.out.print(data[i] + " ");  
  31.         }  
  32.     }  
  33.   
  34. }  
我简单的讲解一下过程：思路上从待排序的数据中选出一个，插入到前面合适的位置，耗时点在插入方面，合适的位置意味着我们需要进行比较找出哪是合适的位置，举个例子：对于9,2,7,19,100,97,63,208,55,78这组数，第一个数9前面没有，不做操作，当第一个数完后，剩下的数就是待排序的数，我们将要从除去9开始的书中选出一个插入到前面合适的位置，拿到2后，放在tmp上，进行注释中的2处的代码，2处的代码就是通过循环找出这个合适的位置，发现比tmp大的数，立即将该数向后移动一位（这样做的目的是：前面需要空出一位来进行插入），最后通过注释3处的代码将数插入。

本排序适合：基本有序的数据

二、选择排序（O(n2)、不稳定）
与直接插入排序正好相反，选择排序是从待排序的数中选出最小的放在已经排好的后面，这个算法选数耗时。

[java] view plain copy
 在CODE上查看代码片派生到我的代码片
  1. package com.xtfggef.algo.sort;  
  2.   
  3. public class SelectSort {  
  4.   
  5.     static int data[] = { 9, 2, 7, 19, 100, 97, 63, 208, 55, 78 };  
  6.   
  7.     public static void selectSort() {  
  8.         int i, j, k, tmp = 0;  
  9.         for (i = 0; i < data.length - 1; i++) {  
  10.             k = i;  
  11.             for (j = i + 1; j < data.length; j++)  
  12.                 if (data[j] < data[k])  
  13.                     k = j;  
  14.             if (k != i) {  
  15.                 tmp = data[i];  
  16.                 data[i] = data[k];  
  17.                 data[k] = tmp;  
  18.             }  
  19.         }  
  20.     }  
  21.     public static void main(String[] args) {  
  22.         print();  
  23.         System.out.println();  
  24.         selectSort();  
  25.         System.out.println();  
  26.         print();  
  27.     }  
  28.   
  29.     static void print() {  
  30.         for (int i = 0; i < data.length; i++) {  
  31.             System.out.print(data[i] + " ");  
  32.         }  
  33.     }  
  34.   
  35. }  
通过循环，找出最小的数的下标，赋值于k，即k永远保持待排序数据中最小的数的下标，最后和当前位置i互换数据即可。

三、快速排序（O(nlogn)、不稳定）

快速排序简称快排，是一种比较快的排序，适合基本无序的数据，为什么这么说呢？下面我说下快排的思路：

设置两个指针：i和j，分别指向第一个和最后一个，i像后移动，j向前移动，选第一个数为标准（一般这样做，当然快排的关键就是这个“标准”的选取），从后面开始，找到第一个比标准小的数，互换位置，然后再从前面，找到第一个比标准大的数，互换位置，第一趟的结果就是标准左边的都小于标准，右边的都大于标准（但不一定有序），分成两拨后，继续递归的使用上述方法，最终有序！代码如下：

[java] view plain copy
 在CODE上查看代码片派生到我的代码片
  1. package com.xtfggef.algo.sort;  
  2.   
  3. public class QuickSortTest {  
  4.   
  5.     static class QuickSort {  
  6.   
  7.         public int data[];  
  8.   
  9.         private int partition(int array[], int low, int high) {  
  10.             int key = array[low];  
  11.             while (low < high) {  
  12.                 while (low < high && array[high] >= key)  
  13.                     high--;  
  14.                 array[low] = array[high];  
  15.                 while (low < high && array[low] <= key)  
  16.                     low++;  
  17.                 array[high] = array[low];  
  18.             }  
  19.             array[low] = key;  
  20.             return low;  
  21.         }  
  22.   
  23.         public int[] sort(int low, int high) {  
  24.             if (low < high) {  
  25.                 int result = partition(data, low, high);  
  26.                 sort(low, result - 1);  
  27.                 sort(result + 1, high);  
  28.             }  
  29.             return data;  
  30.         }  
  31.     }  
  32.   
  33.     static void print(int data[]) {  
  34.         for (int i = 0; i < data.length; i++) {  
  35.             System.out.print(data[i] + " ");  
  36.         }  
  37.     }  
  38.   
  39.     public static void main(String[] args) {  
  40.         int data[] = { 20, 3, 10, 9, 186, 99, 200, 96, 3000 };  
  41.         print(data);  
  42.         System.out.println();  
  43.         QuickSort qs = new QuickSort();  
  44.         qs.data = data;  
  45.         qs.sort(0, data.length - 1);  
  46.         print(data);  
  47.     }  
  48. }  

看看上面的图，基本就明白了。


四、冒泡排序（稳定、基本有序可达O(n)，最坏情况为O(n2)）

冒泡排序是一种很简单，不论是理解还是时间起来都比较容易的一种排序算法，思路简单：小的数一点一点向前起泡，最终有序。

[java] view plain copy
 在CODE上查看代码片派生到我的代码片
  1. package com.xtfggef.algo.sort;  
  2.   
  3. public class BubbleSort {  
  4.   
  5.     static int data[] = { 9, 2, 7, 19, 100, 97, 63, 208, 55, 78 };  
  6.   
  7.     public static void bubbleSort() {  
  8.         int i, j, tmp = 0;  
  9.         for (i = 0; i < data.length - 1; i++) {  
  10.             for (j = data.length - 1; j > i; j--) {  
  11.                 if (data[j] < data[j - 1]) {  
  12.                     tmp = data[j];  
  13.                     data[j] = data[j - 1];  
  14.                     data[j - 1] = tmp;  
  15.                 }  
  16.             }  
  17.         }  
  18.     }  
  19.   
  20.     public static void main(String[] args) {  
  21.         print();  
  22.         System.out.println();  
  23.         bubbleSort();  
  24.         System.out.println();  
  25.         print();  
  26.     }  
  27.   
  28.     static void print() {  
  29.         for (int i = 0; i < data.length; i++) {  
  30.             System.out.print(data[i] + " ");  
  31.         }  
  32.     }  
  33.   
  34. }  


五、堆排序

我们这里不详细介绍概念，堆的话，大家只要记得堆是一个完全二叉树（什么是完全二叉树，请不懂的读者去查资料），堆排序分为两种堆，大顶堆和小顶堆，大顶堆的意思就是堆顶元素是整个堆中最大的，小顶堆的意思就是堆顶元素是整个堆中最小的，满足：任何一非叶节点的关键字不大于或者不小于其左右孩子节点的关键字。堆排序是一个相对难理解的过程，下面我会较为清楚、详细的讲解一下堆排序。堆排序分为三个过程：

建堆：从一个数组顺序读取元素，建立一个堆（完全二叉树）

初始化：将堆进行调整，使得堆顶为最大（最大堆）或者最小（最小堆）的元素

维护：将堆顶元素出堆后，需要将堆的最后一个节点补充到堆顶，因为这样破坏了堆的秩序，所以需要进行维护。下面我们图示一下：

一般情况，建堆和初始化同步进行，

最后为如下所示，即为建堆、初始化成功。

我们可以观察下这个最大堆，看出堆顶是整个堆中最大的元素，而且除叶子节点外每个节点都大于其子节点。下面的过程就是当我们输出堆顶元素后，对堆进行维护。

过程是这样：将堆顶元素出堆后，用最后一个元素补充堆顶元素，这样破坏了之前的秩序，需要重新维护堆，在堆顶元素的左右节点中选出较小的和堆顶互换，然后一直递归下去，所以每次出一个元素，需要一次维护，堆排序适合解决topK问题，能将复杂度降到nlogK。下面是代码：

[java] view plain copy
 在CODE上查看代码片派生到我的代码片
  1. package com.xtfggef.algo.sort;  
  2.   
  3. public class HeapSort {  
  4.     private