1.概述

简单排序：冒泡排序、选择排序、插入排序
高级排序：快速排序、归并排序、希尔排序
相关算法知识：划分、递归、二分查找

2.冒泡排序

2.1原理：

  1. （1）从第一个数据开始，与第二个数据相比较，如果第二个数据小于第一个数据，则交换两个数据的位置<br />    （2）指针由第一个数据移向第二个数据，第二个数据与第三个数据相比较，如果第三个数据小于第二个数据，则交换两个数据的位置<br />    （3）以此类推，完成第一轮排序。第一轮排序结束后，最大的元素被移到了最右面<br />    （4）依照上面的过程进行第二轮排序，将第二大的排到倒数第二的位置<br />    （5）重复上述过程，每排完一轮，比较的此处就减少一次，最后从左到右依次增大

2.2动图演示

Java排序算法的分析与实现 - 图1

2.3例子：

  1.  待序数据：7，6，9，8，5，1<br />     第一轮排序过程：<br />
指针先指向7，7和6比较，6<7,交换6和7的位置，结果为：6，7，9，8，5，1
指针指向第二个元素7，7和9比较，9>7，不用交换位置，结果仍为：6，7，9，8，5，1
指针指向第三个元素9，9和8比较，9>8，交换9和8 的位置，结果为：6，7，8，9，5，1
指针指向第四个元素9，9和5比较，9>5，交换9和5 的位置，结果为：6，7，8，5，9，1
指针指向第五个元素9，9和1比较，9>1，交换9和1 的位置，结果为：6，7，8，5，1，9 
  1.   第一轮排序结束后，最大的数字9被移到了最右边<br />      进行第二轮排序，过程同上，知识由于最大的9已经放到了最右边，一次不用比较9了，少了一次比较，第二轮结束的结果为：6，7，5，1，8，9<br />      第三轮排序结果为：6，5，1，7，8，9<br />      第四轮排序结果为：5，1，6，7，8，9<br />      第五轮排序结果为：1，5，6，7，8，9<br />      最终排序结果为：1,5,6,7,8,9，由上可知N个数据排序，需要进行N-1轮排序；第i轮排序需要比较的次数为N-i次。

2.4编码思想：

  1.   需要两层循环，第一层循环i表示排序的轮数，第二层循环j表示比较的次数

2.5代码实现

  1. package online.shixun.sort;
  3. /**
  4.  * 创建一个BubbleSort类
  5.  */
  6. public class BubbleSort {
  8.     public static void main(String[] args) {
  10.         //定义一个数组num存储要排序的数列
  11.         int[] num = {7,6,9,8,5,1};
  13.         //外层循环，需要比对的次数
  14.         for(int i =0 ;i < num.length;i++){
  16.             //内循环，指针指向的值变化
  17.             for(int j =0;j<num.length-1;j++){
  19.                 //if语句判断，如果前一个数值比后一个大，则交换位置
  20.                 if(num[j]>num[j+1]){
  21.                     int var = num[j];
  22.                     num[j] = num[j+1];
  23.                     num[j+1] = var;
  24.                 }
  25.             }
  26.         }
  28.         //for循环遍历输出数组
  29.         for(int i : num){
  30.             System.out.print(i+"\t");
  31.         }
  32.     }
  33. }

编译结果：
image.png

3.选择排序

3.1简介

  1.   选择排序是一种简单直观的排序算法，无论什么数据进去都是O（n²）的时间复杂度。所以用到它的时候，数据规模越小越好。唯一的好处可能就是不占用额外的外存空间。

3.2算法步骤

  1.   首先在面未排序序列中找到最小（大）元素，存放到排序序列的起始位置。<br />      在从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。<br />      重复第二步，直到所有元素均排序完毕。

3.3动图演示

Java排序算法的分析与实现 - 图3

3.3代码实现

待序数据：7，6，9，8，5，1

  1. package online.shixun.demo01;
  3. /**
  4.  * 定义一个SelectionSort类,选择排序
  5.  */
  6. public class  SelectionSort{
  8.     public static void main(String[] args) {
  10.         //定义一个数组存储待排序数据
  11.         int[] nums ={7,6,9,8,5,1};
  13.         //外层for循环，总共要进行N-1轮比较
  14.         for(int i=0;i < nums.length;i++){
  15.             //初始最小数下标定义为i
  16.             int min = i;
  18.             //内层循环，每轮进行比较的次数
  19.             for(int j = i+1;j<nums.length;j++){
  21.                 //如果下标j的数组值小于当前最小值，则最小值的下标为j
  22.                 if(nums[j]<nums[min]){
  23.                     min = j;
  24.                 }
  25.             }
  27.             //如果i不等于当前最小值的下标，则交换连个数的位置
  28.             if(i!=min){
  29.                 int tmp = nums[i];
  30.                 nums[i] = nums[min];
  31.                 nums[min]= tmp;
  32.             }
  33.         }
  35.         //for循环遍历输出数组
  36.         for(int a:nums){
  37.             System.out.print(a+"\t");
  38.         }
  39.     }
  40. }

编译结果
image.png

4.插入排序

4.1简介

  1.  插入排序是一种最简单直观的排序算法，它的工作原理是通过构建有序序列，对未排序数据，在已排序序列找那个从后向前扫描，找到相应的位置并插入

4.2算法步骤

  1.  将第一待牌序列序列第一个元素看做一个有序数列，把第二个元素到最后一个元素当成是未排序序列。<br />     从头到尾一次扫描未排序序列，将扫描到每个元素插入有序序列的适当位置。（如果待插入的元素与有序序列中的某个元素相等，则将待插入元素插入到相等元素的后面）

4.3动图演示

Java排序算法的分析与实现 - 图5

4.4代码实现

待序数据：7，6，9，8，5，1

  1. package online.shixun.demo02;
  3. /**
  4.  * 创建一个InsertSort类，插入排序
  5.  */
  6. public class InsertSort {
  8.     public static void main(String[] args) {
  10.         //定义数组
  11.         int[] nums ={7,6,9,8,5,1};
  13.         //外层循环，从下标为1的元素开始选择合适的位置插入
  14.         // 因为下标为0的元素只有一个所以默认为有序数列
  15.         for(int i = 1;i < nums.length;i++){
  17.             //记录要插入的数据
  18.             int tmp = nums[i];
  20.             //从已经排序的序列最右边开始比较，找的比其小的数
  21.             int j = i;
  22.             while(j > 0&& tmp < nums[j - 1]){
  23.                 nums[j] = nums[j - 1];
  24.                 j = j -1;
  25.             }
  27.             //存在比其小的数，插入
  28.             if(j != i){
  29.                 nums[j] = tmp;
  30.             }
  31.         }
  33.         //for循环遍历输出数组
  34.         for(int a : nums){
  35.             System.out.print(a+"\t");
  36.         }
  37.     }
  38. }

编译结果
image.png

5.快速排序

5.1简介

  1.  快速排序使用分治策略来吧一个串行（list）分为两个子串行。<br />     快速排序又是一种分而治之思想在排序算法上的典型yingy。本质上来看，快速排序应该算是在冒泡排序基础上的递归分治法。<br />     快速排序最坏的运行情况是O（n²），比如说顺序数列的快排。但是它的平摊期望时间是O（nlogn）几号中隐含的常熟因子很小，所以，对绝大多数顺序型较弱的随机数列而言，快速排序总是优于归并排序。

5.2算法步骤

  1.  1.从数列中跳出一个元素，称为“基准”（pivot）；<br />     2.重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的排在基准的后面（相同的数可以放在任一边）。在这个分区退出后，该基准就处于数列的中间位置。这个称谓分区（partition）操作<br />     3.递归的（recursive）把小于基准值的元素的子数列和大于基准值的子数列排序

5.3动图演示

Java排序算法的分析与实现 - 图7

5.4代码实现

待序数列：5，3，8，13，2，9，17，1，12

  1. package online.shixun.demo01;
  3. public class QuickSort {
  7.     public static void main(String[] args) {
  9.         //定义静态待序数组
  10.          int[] arr = {5,3,8,13,2,9,17,1,12};
  11.         //调用方法
  12.         quickSort(arr,0,arr.length-1);
  14.         //for循环遍历输出排序后的数组
  15.         for(int a : arr){
  16.             System.out.print(a+"\t");
  17.         }
  18.     }
  20.     /**
  21.      *构造方法切割数组为两半，从下标为0作为左边开始调用partition方法
  22.      * @param arr
  23.      * @param left
  24.      * @param right
  25.      * @return排序后的数组
  26.      */
  27.     private static int[] quickSort(int[] arr,int left,int right){
  28.         if(left<right){
  29.             int partitionIndex = partition(arr,left,right);
  31.             //调用quickSort方法对排序后基准的左边再进行分割成两半。
  32.             // 下标为0作为左边，再次进行排序
  33.             quickSort(arr,left,partitionIndex-1);
  35.             //调用方法quickSort对排序后的数组右边进行分割成两半。
  36.             //第一次分割的右边的最左边作为左边，再次进行排序
  37.             quickSort(arr,partitionIndex+1,right);
  38.         }
  39.         return arr;
  40.     }
  42.     /**
  43.      *构造方法，设立基准将数组分为两半，比基准大的数放在右边，小的放在左边
  44.      * @param arr
  45.      * @param left
  46.      * @param right
  47.      * @return左边数组的长度
  48.      */
  49.     private static int partition(int[] arr,int left,int right){
  51.         //设置基准
  52.         int pivot = left;
  53.         int index = pivot + 1;
  55.         //for循环从基准右边开始扫描
  56.         // 如果比基准的数值小，则调用swap方法交换基准和该数在数组中的位置
  57.         for(int i = index; i<=right;i++){
  58.             if(arr[i]<arr[pivot]){
  59.                 swap(arr,i,index);
  60.                 index++;
  61.             }
  62.         }
  63.         swap(arr,pivot,index - 1);
  64.         return index - 1;
  65.     }
  67.     /**
  68.      * 构造方法，交换待序数组中两个数的位置
  69.      * @param arr
  70.      * @param i
  71.      * @param j
  72.      */
  73.     private static void swap(int[] arr,int i,int j){
  74.         int temp = arr[i];
  75.         arr[i] = arr[j];
  76.         arr[j] = temp;
  77.     }
  78. }

编译结果
image.png

6.希尔排序

6.1简介

希尔排序，也称递减增量排序算法，是插入排序的一种更高效的改进版本。但希尔排序是非稳定排序算法。
希尔排序是基于插入排序的以下两点性质而提出改进方法的：

  • 插入排序在对几乎已经排好序的数据操作时，效率高，即可以达到线性排序的效率；
  • 但插入排序一般来说是低效的，因为插入排序每次只能将数据移动一位；

希尔排序的基本思想是：先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录”基本有序”时，再对全体记录进行依次直接插入排序。

6.2算法步骤

选择一个增量序列 t1，t2，……，tk，其中 ti > tj, tk = 1；
按增量序列个数 k，对序列进行 k 趟排序；
每趟排序，根据对应的增量 ti，将待排序列分割成若干长度为 m 的子序列，分别对各子表进行直接插入排序。仅增量因子为 1 时，整个序列作为一个表来处理，表长度即为整个序列的长度。

6.3动图演示

Java排序算法的分析与实现 - 图9

6.4代码实现

  1. package online.shixun.demo;
  3. /**
  4.  * 希尔排序
  5.  */
  6. public class ShellSort {
  8.     public static void main(String[] args) {
  10.         int[] nums = {4, 7, 24, 5, 3, 35, 14, 56, 9, 12};
  12.         doSort(nums);
  13.         show(nums);
  14.     }
  16.     private static void doSort(int[] arr) {
  18.         int gap = 1;
  19.         while (gap < arr.length) {
  20.             gap = gap * 3 + 1;
  21.         }
  23.         while (gap > 0) {
  24.             for (int i = gap; i < arr.length; i++) {
  25.                 int tmp = arr[i];
  26.                 int j = i - gap;
  27.                 while (j >= 0 && arr[j] > tmp) {
  28.                     arr[j + gap] = arr[j];
  29.                     j -= gap;
  30.                 }
  31.                 arr[j + gap] = tmp;
  32.             }
  33.             gap = (int) Math.floor(gap / 3);
  34.         }
  35.     }
  37.     private static void show(int[] nums) {
  39.         for (int i : nums) {
  40.             System.out.print(i + "\t");
  41.         }
  42.     }
  43. }

编译结果
image.png