插入排序

直接插入排序：

　　　　当插入第i个数据元素k时，由前i-1个数据元素组成已排序的数据序列，将k与数据序列中各数据元素依次进行比较后，插入到数据序列的适当位置，使得插入后的数据序列仍是排序的。

　　　　直接插入排序算法是稳定的，时间复杂度为O(n^2)。

 /*

  * 插入排序

  *     1.外层循环（循环控制变量i）的迭代是为了获取已排好序的子数列

  *     2.内层循环（循环控制变量k）将list[i]插入到从list[0]到list[i-1]的子数列中

  */

 public static void insertionSort(int[] array) {

     for (int i = 1; i < array.length; i++) {

         int minValue = array[i];

         int k;

         for (k = i - 1;k >= 0 && minValue < array[k]; k--) {

             array[k + 1] = array[k];

         }

         array[k + 1] = minValue;

     }

 }

希尔排序：

　　　　排序之初，允许数据元素做较大的移动，而当数据元素接近目的地时，再做较小的移动。这样做可使排序过程加快。希尔排序的算法思想非常简单，但如何选择增量以产生最好的排序效果，至今仍没定论。

　　　　希尔排序算法是不稳定的，所需的时间取决于每次排序时增量的个数和增量的取值，若增量的取值比较合理，希尔排序算法的时间复杂度约为O(n(log_2n)^2)。

交换排序

冒泡排序：

　　　　将相邻的两个数据元素按关键字进行比较，如果反序，则交换。对于一个待排序的数据序列，经一趟排序后，最大值数据元素移到最后位置，其它值较大的数据元素也向最终位置移动，此过程称为一趟起泡。

　　　　冒泡排序算法是稳定的，时间复杂度为O(n^2)。

快速排序：

　　　　快速排序是目前平均性能较好的一种排序算法。

　　　　在待排序的数据序列中任意选择一个值作为基准值，由序列的两端交替地向中间进行比较、交换，使得所有比基准值晓得元素都处于序列的左端，比基准值大的元素都处于序列的右端，这样序列就被划分成两个子序列。再对两个子序列分别进行同样的操作，直到子序列的长度为1时，则已排好序。每趟排序完，作为基准值的数据元素需要找到它在排好序的序列中的最终位置。

选择排序：

　　设待排序的数据序列有n个元素，第1趟排序，比较n个元素，选择关键字最小的元素，将其交换到序列的第1个位置上；第2趟排序，在余下的n-1个元素中，再选取关键字最小的元素，交换到序列的第2个位置上.....经过n-1趟排序，n个元素的数据序列则按递增次序排序完成。

　　直接选择排序算法是不稳定的

 /*

  * 选择排序

  *     1.选择排序法先找到数列中最小的数

  *     2.然后将它放在数列的最前面

  *     3.在剩下的数中，循环1、2操作

  */

 public static void selectionSort(int[] array) {

     for (int i = 0; i < array.length - 1; i++) {

         int minValue = array[i];

         int minIndex = i;

         for (int j = i + 1;j < array.length;j++) {

             if (array[j] < minValue) {

                 minValue = array[j];

                 minIndex = j;

             }

         }

         if (minIndex != i) {

             array[minIndex] = array[i];

             array[i] = minValue;

         }

     }

 }

归并排序：

　　归并排序算法可以递归地描述为：算法将数组分为两半，对每部分递归地应用归并排序。在两部分都排好序后，对它们进行归并。

　　递归调用持续将数组划分为子数组，直到每个子数组只包含一个元素。然后，该算法将这些小的子数组归并为稍大的有序子数组，直到最后形成一个有序的数组。

 /**

  * @author zhengbinMac

  */

 public class mergeSort {

     public static void main(String[] args) {

         int[] list = {2, 3, 2, 5, 6, 1, -2, 3, 14, 12};

         mergeSort(list);

         for (int i = 0; i < list.length; i++) {

             System.out.print(list[i]+" ");

         }

     }

     public static void mergeSort(int[] list) {

         if(list.length > 1) {

             // 拆分过程

             // 第一半儿

             int[] firstHalf = new int[list.length / 2];

             System.arraycopy(list, 0, firstHalf, 0, list.length / 2);

             // 将这一半儿再拆成两半儿

             mergeSort(firstHalf);

             // 第二半儿

             int secondHalfLength = list.length - list.length / 2;

             int[] secondHalf = new int[secondHalfLength];

             System.arraycopy(list, list.length / 2, secondHalf, 0, secondHalfLength);

             // 将这一半儿再拆成两半儿

             mergeSort(secondHalf);

             // 将两半儿数组归并成一个新的有序数组temp

             int[] temp = merge(firstHalf, secondHalf);

             // 将temp赋给原始数组list

             System.arraycopy(temp, 0, list, 0, temp.length);

         }

     }

     private static int[] merge(int[] list1, int[] list2) {

         // 将拆分出来的两个数组归并为排好序的一个数组

         int[] temp = new int[list1.length + list2.length];

         int current1 = 0; // 指向list1当前考虑的元素

         int current2 = 0; // 指向list2当前考虑的元素

         int current3 = 0; // 指向temp当前考虑的元素

         while(current1 < list1.length && current2 < list2.length) {

             if(list1[current1] < list2[current2]) {

                 // 如果较小的元素在list1中，current1增加1

                 temp[current3++] = list1[current1++];

             }else {

                 // 如果较小的元素在list2中，current2增加1

                 temp[current3++] = list2[current2++];

             }

         }

         // 如果list1和list2中仍有未移动的元素，就将它们复制到temp中

         while(current1 < list1.length) {

             temp[current3++] = list1[current1++];

         }

         while(current2 < list2.length) {

             temp[current3++] = list2[current2++];

         }

         // 将temp作为一个新的有序数组返回

         return temp;

     }

 }

 package One;

 public class Test_sort {

     public static void main(String[] args) {

         int[] a = { 2, 9, 5, 4, 8, 1 };

         // sort(bubble_sort);

         quick_sort(a, 0, a.length - 1);

         for (int i = 0; i < a.length; i++) {

             System.out.print(a[i] + " ");

         }

     }

     // 冒泡排序

     public static int[] bubble_sort(int[] a) {

         // 设置判断，进行优化

         // 如果某次遍历中没有发生交换，那么就不用再进行下去，因为排序已完成

         boolean ac = true;

         for (int k = 1; k < a.length & ac; k++) {

             ac = false;

             for (int i = 0; i < a.length - 1; i++) {

                 if (a[i] > a[i + 1]) {

                     int temp = a[i];

                     a[i] = a[i + 1];

                     a[i + 1] = temp;

                     ac = true;

                 }

             }

         }

         return a;

     }

     // 快速排序

     public static int[] quick_sort(int s[], int l, int r) {

         if (l < r) {

             // Swap(s[l], s[(l + r) / 2]); //将中间的这个数和第一个数交换 参见注1

             int i = l, j = r, x = s[l];

             while (i < j) {

                 // 从右向左找第一个小于x的数

                 while (i < j && s[j] >= x)

                     j--;

                 if (i < j)

                     s[i++] = s[j];

                 // 从左向右找第一个大于等于x的数

                 while (i < j && s[i] < x)

                     i++;

                 if (i < j)

                     s[j--] = s[i];

             }

             s[i] = x;

             quick_sort(s, l, i - 1); // 递归调用 从右至左

             quick_sort(s, i + 1, r); // 从左至右

         }

         return s;

     }

 }

巴特西

一天一个Java基础——排序