排序算法

排序算法有很多，包括插入排序，冒泡排序，堆排序，归并排序，选择排序，计数排序，基数排序，桶排序，快速排序等。插入排序，堆排序，选择排序，归并排序和快速排序，冒泡排序都是比较排序，它们通过对数组中的元素进行比较来实现排序，其他排序算法则是利用非比较的其他方法来获得有关输入数组的排序信息。

1 冒泡排序

冒泡排序（Bubble Sort），是一种计算机科学领域的较简单的排序算法。

这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端（升序或降序排列），就如同碳酸饮料中二氧化碳的气泡最终会上浮到顶端一样，故名“冒泡排序”。

1.1 原理

  1. 比较相邻的元素。如果第一个比第二个大，就交换他们两个。
  2. 对每一对相邻元素做同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。
  3. 针对所有的元素重复以上的步骤，除了最后一个。
  4. 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

1.2 算法实现

Python3

  1. def bubble_sort(nums):
  2.     for i in range(len(nums) - 1):  # 这个循环负责设置冒泡排序进行的次数
  3.         for j in range(len(nums) - i - 1):  # j为列表下标
  4.             if nums[j] > nums[j + 1]:
  5.                 nums[j], nums[j + 1] = nums[j + 1], nums[j]
  6.     return nums

Java

  1. public static void bubbleSort(int []arr) {
  2.         for(int i =1;i<arr.length;i++) { 
  3.             for(int j=0;j<arr.length-i;j++) {
  4.                 if(arr[j]>arr[j+1]) {
  5.                     int temp = arr[j];
  6.                     arr[j]=arr[j+1];
  7.                     arr[j+1]=temp;
  8.             }
  9.         }
  10.     }
  11. }

2 选择性排序

选择排序（Selection sort）是一种简单直观的排序算法。它的工作原理是：第一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，然后再从剩余的未排序元素中寻找到最小（大）元素，然后放到已排序的序列的末尾。以此类推，直到全部待排序的数据元素的个数为零。选择排序是不稳定的排序方法。

2.1 算法实现

  1. public static void selectionSort(int[] arr){
  3.        for (int i = 0; i < arr.length - 1; i++) {    
  4.             int  min = i;
  5.             for (int j = i + 1; j < arr.length; j++) {
  6.                   if (arr[min] > arr[j]) {
  7.                        min = j;
  8.                   }
  9.             }
  10.             if (min != i) {
  11.                int tmp = arr[min];
  12.                arr[min] = arr[i];
  13.                arr[i] = tmp;
  14.             }             
  15.       }
  17. }

3 插入排序

插入排序（Insertion sort）是一种简单直观且稳定的排序算法。

3.1 原理

每步将一个待排序的记录，按其关键码值的大小插入前面已经排序的文件中适当位置上，直到全部插入完为止。

3.1 解释

比如 [6, 5, 2, 7, 3, 2, 1]

左端的数字已经完成排序，取出尚未操作的左端数字，比如5，与已经操作的数字6比较，5比6小，所以交换位置；

依次类推，将2和已经排序的5，6比较，2比5小，所以插入第一个；

7再和2，5，6比，最大，所以插入到最后一个。

算法实现

  1. def insert_sort(lst):
  2.     for i in range(1,len(lst)):
  3.         tmp = lst[i]
  4.         j = i - 1
  5.         while j >= 0 and tmp < lst[j]:
  6.             lst[j + 1] = lst[j]
  7.             j = j - 1
  8.         lst[j + 1] = tmp
  9.     return lst

堆排序

利用堆的数据结构。

等以后了解的堆再写。

归并排序

首先，我们将数字分成两个一组。

然后开始合并每个组。合并时按照数字的升序移动，使得合并后的数字在组内按升序排列。

比如：[1, 3, 5, 6, 8, 2, 4]，分成[1, 3],[5, 6],[8, 2]和[4]。

第一组和第二组合并时，先比较开头的数字1和5，再比较3和6，如果前者比后者大则交换位置，依次类推，最终合并成一个数列。

快速排序

特点是数字的比较和交换次数少，在许多情况下可以高速排序。

比较复杂。