快速排序 Quick Sort

快速排序是一种高效的排序方法，于 1963 年由 Tony Hoare 发布。

原理

快速排序是一种分治（Divide-and-Conquer）算法。它的主要思路是：

归并排序 Merge Sort

归并排序是一个高效的、基于比较的排序算法。

原理

归并排序是一个典型的分治(Divide and Conquer)算法。具体思路如下：

• 将未排序的序列分割成 n 个只有单个元素的子序列。（单个元素的序列认为是有序的）
• 重复的将各个子序列合并成新的有序的序列，直到只有一个序列即为排好序的序列。

图示

可以通过动画演示理解, 以下网上找的两个动画。如果你想操作不同的参数来演示，可以上这个网站visualgo.net动手试试。

插入排序 Insertion sort

原理

先看看Wikipedia的定义：

Insertion sort algorithm iterates, consuming one input element each repetition, and growing a sorted output list. Each iteration removes one element from the input data, finds the location it belongs within the sorted list, and inserts it there. It repeats until no input elements remain.

选择排序 Selection sort

原理

先看看Wikipedia的定义：

The Selection sort algorithm divides the input list into two parts: the sublist of items already sorted and the sublist of items remaining to be sorted that occupy the rest of the list. Initially, the sorted sublist is empty and the unsorted sublist is the entire input list. The algorithm proceeds by finding the smallest element in the unsorted sublist, exchanging it with the leftmost unsorted element, and moving the sublist boundaries one element to the right. .

冒泡排序 Bubble sort

原理

先看看Wikipedia的定义：

Bubble sort is a simple sorting algorithm that repeatedly steps through the list to be sorted, compares each pair of adjacent items and swaps them if they are in the wrong order. The pass through the list is repeated until no swaps are needed, which indicates that the list is sorted.

算法特性及大O记法

排序算法

排序算法(Sorting algorithms)是什么？ Wikipedia 如是说:

In computer science, a sorting algorithm is an algorithm that puts elements of a list in a certain order.