- 冒泡排序
- 选择排序
-
插入排序
- 二分插入排序
- 希尔排序
- 堆排序
- 归并排序
- 快速排序
-
交换排序类：
- 冒泡排序
- 快速排序
-
选择排序类：
- 简单选择排序
- 堆排序
-
插入排序类
- 直接插入排序
- 二分插入排序
- 希尔排序
#1.排序的基本概念和分类
1.1 排序的稳定性
假设Ki = Kj(1 =< i <=n,1=< j <=n,i != j)，且在排序前的序列中Ri领先于Rj(即i < j)。如果排序后Ri仍领先于Rj，则称所用的排序算法是稳定的；反之，若可能使得排序后的序列中Rj领先于Ri，则称所有的排序算法不稳定。
1.2 内排序和外排序
根据在排序过程中带排序的记录是否全部放置在内存中，排序分为：内排序和外排序。
- 内排序是在排序过程中，带排序的所有记录全部被放置在内存中。
- 外排序是由于排序记录个数太多，不能同时放置在内存，整个排序过程需要在内外存之间多次交换数据才能进行。
对于内排序来说，排序算法的性能主要受3个方面影响：
- 时间性能
- 辅助空间
- 算法的复杂性
根据排序过程中借助的主要操作，我们把内排序分为：插入排序、交换排序、选择排序和归并排序。
#2.排序算法
2.1 冒泡排序
冒泡排序（Bubble Sort）是一种交换排序，它的基本思想是：两两比较相邻记录的关键字，如果反序则交换，直到没有反序的记录为止。
排序流程：
- 比较相邻的元素。如果第一个比第二个大，就交换他们两个。
- 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。
- 针对所有的元素重复以上的步骤，除了最后一个。
- 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。
示意图：
Bubble Sort
Code
template<typename T>
void bubble_sort(T arr[], int n)
{
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n - 1 - i; j++)
{
if (arr[j] > arr[j+1])
{
swap(arr[j],arr[j+1]);
}
}
}
}
时间复杂度
O(n^2)
辅助空间
O(1)
稳定性
稳定
2.2 选择排序
简单选择排序法（Selection Sort）就是通过n-i次关键字间的比较，从n-i+1个记录中选出关键字最小的记录，并和第i（1 =< i <= n）个记录进行交换。
排序流程：
- 首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，
- 从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。
示意图：
Selection Sort
Code
/*简单选择排序*/
template<typename T>
void selection_sort(T arr[], int n)
{
//One by one move boundary of unsorted subarray.
for (int i = 0; i < n - 1; i++)
{
int min_idx = i;
//Find the minimum element in unsorted array.
for (int j = i + 1; j < n; j++)
if (arr[j] < arr[min_idx])
min_idx = j;
//Swap the founded minimum element with the first element.
if(min_idx != i)
swap(&arr[i], &arr[min_idx]);
}
}
时间复杂度
O(n^2)
辅助空间
O(1)
稳定性
不稳定
注意：选择排序是不稳定性排序算法：
{1,6,5,6,2,1}第2次选择的最小元素1，然后和第一个6进行交换，从而改变两个6的相对顺序。
2.3 插入排序
直接插入排序
直接插入排序（Straight Insertion Sort）的基本操作将一个记录插入到已经排好序的有序表中，从而得到一个新的、记录数增1的有序表。
排序流程
- 从第一个元素开始，该元素可以认为已经被排序
- 取出下一个元素，在已经排序的元素序列中从后向前扫描
- 如果该元素（已排序）大于新元素，将该元素移到下一位置
- 重复步骤3，直到找到已排序的元素小于或者等于新元素的位置
- 将新元素插入到该位置后
- 重复步骤2~5
示意图：
Insertion Sort
Code
/*直接插入排序*/
template<typename T>
void straight_insertion_sort(T arr[], int n) {
int i, j;
for (i = 1; i < n; i++)
{
T key = arr[i];
j = i - 1;
/*Move elements of arr[0..i-1],that are greater than
key,to one position ahead of their current position.
*/
while (j >= 0 && arr[j] > key)
{
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = key;
}
}
时间复杂度
O(n^2)
辅助空间
O(1)
稳定性
稳定
二分插入排序
对于插入排序如果比较次数比较多的话可以采用二分查找来减少比较操作的次数，即二分插入排序。
Code
template<typename T>
void binary_insertion_sort(T arr[],int n) {
for (int i = 1; i < n; i++)
{
int key = arr[i];
int left = 0;
int right = i - 1;
while (left <= right)
{
int mid = (left + right) / 2;
if (arr[mid] > key)
{
right = mid - 1;
}
else {
left = mid + 1;
}
}
//Move all elements that bigger than the key.
for (int j = i - 1; j >= left; j--)
{
arr[j + 1] = arr[j];
}
arr[left] = key;
}
}
希尔排序
希尔排序是插入排序的一种又称“递减增量排序”，是直接插入排序的一种更高效的改进版本。希尔排序是非稳定排序算法。
希尔排序是基于插入排序的以下两点性质而提出改进方法的：
- 插入排序在对几乎已经排好序的数据操作时，效率高，即可以达到线性排序的效率。
- 但插入排序一般来说是低效的，因为插入排序每次只能将数据移动一位。
排序流程
- 先取一个小于n的整数d1作为第一个增量，把文件的全部记录分组。所有距离为d1的倍数的记录放在同一个组中。先在各组内进行直接插入排序。
- 取第二个增量d2<d1重复上述的分组和排序，直至所取的增量=1(<…<d2<d1)即所有记录放在同一组中进行直接插入排序为止。
给定实例的shell排序的排序过程：
假设待排序文件有10个记录，其关键字分别是：49，38，65，97，76，13，27，49，55，04。
增量序列的取值依次为：5，2，1
Shell Sort.jpg
Code
/*Shell Sort*/
template<typename T>
void shell_sort(T arr[], int n) {
//Start with a big gap,then reduce the gap
for (int gap = n >> 2; gap > 0; gap >>= 2)
{
//Do a gapped insertion sort for this gap size.
//The first gap elements a[0..gap-1] are already in gapped order
//keep adding one more element until the entire array is
//gap sorted
for (int i = gap; i < n; i ++)
{
//Add arr[i] to the elements that have been gap sorted
//save arr[i] in temp and make a hole at position i
T key = arr[i];
//shift earlier gap-sorted elements up until the correct
//location for arr[i] is found
int j;
for (j = i; j >= gap && arr[j - gap] > key; j -= gap)
{
arr[j] = arr[j - gap];
}
//Put temp (the original arr[i]) in its correct location.
arr[j] = key;
}
}
}
时间复杂度
O(n^2)
辅助空间
O(1)
稳定性
不稳定
2.4 堆排序
堆排序就是利用堆进行排序的方法。它的基本思想是，将待排序的序列结构造成一个大根堆。此时，整个序列的最大值就是堆顶的根结点。将它移走（其实就是将其与堆数组的末尾元素交换，此时末尾元素就是最大值），然后将剩余n-1个序列重新构造成一个堆，这样就会得到n个元素中的次小值。如此反复执行，即得到一个有序序列。
堆是具有下列性质的完全二叉树：每个结点的值都大于或等于其左右孩子结点的值，称为大根堆；或者每个结点的值都小于或等于其左右孩子结点的值，称为小根堆。
大根堆.png
排序流程
- 利用BUILD-MAX-HEAP将输入数组A[1..n]建成最大堆，其中n=A.length。因为数组中的最大元素总在根结点A[1]中，通过把它与A[n]进行交换，我们可以让该元素放到正确的位置。
- MAX-HEAPIFY利用维护堆的性质
示意图：
Heap Sort
Code
//To heapify a subtree rooted with node i which is
//an index in arr[]. n is the size of heap.
template<typename T>
void max_heapify(T arr[], int n, int i) {
int largest = i;//Initialize largest as root
int l = 2 * i + 1;//left = 2*i + 1
int r = 2 * i + 2;//right = 2*i + 2
//If left child is larger than root.
if (l < n && arr[l] > arr[i])
{
largest = l;
}
//If right child is larger than largest so far.
if (r < n && arr[r] > arr[largest])
{
largest = r;
}
//If largest is not root.
if (largest != i)
{
swap(&arr[largest], &arr[i]);
//Recursively heapify the affected sub-tree.
max_heapify(arr, n, largest);
}
}
template<typename T>
void heap_sort(T arr[], int n) {
//Step1:Build Max heap(rearrange array)
for (int i = n >> 2 - 1; i >= 0; i--)
{
max_heapify(arr, n, i);
}
//One by one extract an element from heap.
for (int i = n - 1; i >= 0; i--)
{
//Move current root to end.
swap(&arr[0], &arr[i]);
//Call max heapify on reduced heap.
max_heapify(arr, i, 0);
}
}
时间复杂度
O(nlogn)
辅助空间
O(1)
稳定性
不稳定
2.5 归并排序
归并排序（Merge Sort）就是利用归并的思想实现的排序方法。它的原理是假设初始序列含有n个记录，则可以看成是n个有序的子序列，每个子序列的长度为1，然后两两归并，得到[n/2]个长度为2或1的有序子序列；再两两归并，如此重复，直至得到一个长度为n的有序序列为止，这种排序方法称为2路归并排序。
排序流程
- 申请两个临时空间，分别存储已经排序的两个子序列。
- 设定索引，最初位置分别为两个已经排序序列的起始位置。
- 比较两个索引所对应的元素，选择相对小的元素放入到arr中，并移动索引指向下一位置。临时数组的索引和merge数组的索引。
- 重复步骤3直到序列末尾。
- 分别拷贝两个子数组中剩余元素（如果存在的话）。
示意图：
Merge Sort
Code
// Merges two subarrays of arr[].
// First subarray is arr[l..m]
// Second subarray is arr[m+1..r]
void merge(int arr[], int l, int m, int r)
{
int i, j, k;
int n1 = m - l + 1;
int n2 = r - m;
/* create temp arrays */
int L[n1], R[n2];
/* Copy data to temp arrays L[] and R[] */
for (i = 0; i < n1; i++)
L[i] = arr[l + i];
for (j = 0; j < n2; j++)
R[j] = arr[m + 1+ j];
/* Merge the temp arrays back into arr[l..r]*/
i = 0; // Initial index of first subarray
j = 0; // Initial index of second subarray
k = l; // Initial index of merged subarray
while (i < n1 && j < n2)
{
if (L[i] <= R[j])
{
arr[k] = L[i];
i++;
}
else
{
arr[k] = R[j];
j++;
}
k++;
}
/* Copy the remaining elements of L[], if there
are any */
while (i < n1)
{
arr[k] = L[i];
i++;
k++;
}
/* Copy the remaining elements of R[], if there
are any */
while (j < n2)
{
arr[k] = R[j];
j++;
k++;
}
}
/* l is for left index and r is right index of the
sub-array of arr to be sorted */
void mergeSort(int arr[], int l, int r)
{
if (l < r)
{
// Same as (l+r)/2, but avoids overflow for
// large l and h
int m = l+(r-l)/2;
// Sort first and second halves
mergeSort(arr, l, m);
mergeSort(arr, m+1, r);
merge(arr, l, m, r);
}
}
时间复杂度
O(nlogn)
辅助空间
O(n)
稳定性
稳定
2.6 快速排序
快速排序（Quick Sort）的基本思想是：通过一趟排序将待排序记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序的目的。
排序流程：
针对一个典型的子数组A[p..r]进行快速排序的三步分治过程：
- 分解：将数组A[p..r]划分为两个（可能为空）子数组A[p..q-1]和A[q+1..r]，使得A[p..q-1]中每一个元素都小于等于A[q]，而A[q]也小于等于A[q+1..r]中的每个元素。其中，计算下标q也是划分过程的一部分。
- 解决：通过递归调用快速排序，对子数组A[p..q-1]和A[q+1..r]进行排序。
- 合并：因为子数组都是原址排序的，所以不需要合并操作：数组A[p..r]已经有序。
Code
/* This function takes last element as pivot, places
the pivot element at its correct position in sorted
array, and places all smaller (smaller than pivot)
to left of pivot and all greater elements to right
of pivot */
int partition (int arr[], int low, int high)
{
int pivot = arr[high]; // pivot
int i = (low - 1); // Index of smaller element
for (int j = low; j <= high- 1; j++)
{
// If current element is smaller than or
// equal to pivot
if (arr[j] <= pivot)
{
i++; // increment index of smaller element
swap(&arr[i], &arr[j]);
}
}
swap(&arr[i + 1], &arr[high]);
return (i + 1);
}
/* The main function that implements QuickSort
arr[] --> Array to be sorted,
low --> Starting index,
high --> Ending index */
void quickSort(int arr[], int low, int high)
{
if (low < high)
{
/* pi is partitioning index, arr[p] is now
at right place */
int pi = partition(arr, low, high);
// Separately sort elements before
// partition and after partition
quickSort(arr, low, pi - 1);
quickSort(arr, pi + 1, high);
}
}
时间复杂度
O(n^2)
辅助空间
O(logn) ~ O(n)
稳定性
不稳定
