一、选择排序
原理
从前往后遍历列表的每个位置，找到应该放在该位置的元素。通俗的说：找到最小的元素放在第一个位置，第二小的元素放在第二个位置，第三小的元素放在第三个位置......
算法复杂度
需要两层循环，第一层循环遍历列表的每个位置，第二层找到该位置之后元素中的最小值，因此算法复杂度为O(n^2)
动画演示
选择排序
算法实现
def select_sort(origin_items):
"""
选择排序
"""
items = origin_items[:]
for i in range(len(items) - 1):
min_index = i
for j in range(i+1, len(items)):
if items[min_index] > items[j]:
min_index = j
items[i], items[min_index] = items[min_index], items[i]
return items
二、冒泡排序
原理
对于每一轮排序，比较前后两个元素，如果前面元素比后面元素大，则交换位置，直到比较完列表最后两个元素。每一轮确定一个元素的位置。一共进行n轮。(n为列表元素个数)
时间复杂度
由于两层循环，第一层控制轮数，第二层从前往后遍历元素用于比较相邻两个元素，所以时间复杂度为O(n^2)
动画演示
冒泡排序.gif
算法实现
def bubble_sort(origin_items):
"""
冒泡排序
"""
items = origin_items[:]
for i in range(len(items)):
flag = False
for j in range(len(items) - 1 - i):
if items[j] > items[j+1]:
items[j], items[j+1] = items[j+1], items[j]
flag = True
if not flag:
break
return items
三、快速排序
原理
首先确定一个基准数（一般选择第一个元素），将比基准数小的放在基准数的左边，比基准数大的放在基准数右边，将左右两边的数列继续按照此逻辑进行。
时间复杂度
需要比较每个数和基准数的大小，同时将列表按二分的方法拆分logn次，因此时间复杂度为O(nlogn)。注意：对于一个已经排好序的列表，需要对列表拆分n次，所以最坏时间复杂度为O(n^2)
动画演示
快速排序.gif
算法实现
Python
def quick_sort(origin_items):
"""
快速排序
"""
def helper(items, start, end):
i, j = start, end
if i < j:
base = items[i]
while i < j:
while i < j and items[j] >= base:
j -= 1
if i < j:
items[i] = items[j]
i += 1
while i < j and items[i] <= base:
i += 1
if i < j:
items[j] = items[i]
j -= 1
items[i] = base
helper(items, start, i-1)
helper(items, j+1, end)
return items
items = origin_items[:]
items = helper(items, 0, len(items)-1)
return items
Java
public class QuickSort {
public int[] quickSort(int[] nums) {
quick(nums, 0, nums.length - 1);
return nums;
}
public void quick(int[] nums, int left, int right) {
if (left > right) return;
int i = left, j = right;
int base = nums[i];
while (i < j) {
while (i < j && nums[j] >= base) j--;
if (i < j) {
nums[i] = nums[j];
i++;
}
while (i < j && nums[i] <= base) i++;
if (i < j) {
nums[j] = nums[i];
j--;
}
}
nums[i] = base;
quick(nums, left, i - 1);
quick(nums, i + 1, right);
}
public static void main(String[] args) {
QuickSort qs = new QuickSort();
int[] nums = {2,4,1,5,2,1,5,7,8,3};
qs.quickSort(nums);
System.out.println(Arrays.toString(nums));
}
题目变形：
四、归并排序
原理
算法采用分治策略，将列表拆分为更小的列表然后递归求解，再将拆分后的结果合并在一起。
时间复杂度
列表拆分为更小列表的时间复杂为O(logn)，合并操作的时间复杂度为O(n)，所以总的时间复杂度为O(nlogn)
动画演示
归并排序.gif
算法实现
- Python
class Solution():
def merge_sort(self, lst):
n = len(lst)
tmp = [0] * n
nums = self.merge(lst, tmp, 0, n - 1)
return nums
def merge(self, lst, tmp, left, right):
if left >= right:
return
mid = left + right >> 1
self.merge(lst, tmp, left, mid)
self.merge(lst, tmp, mid + 1, right)
i, j, pos = left, mid + 1, left
while i <= mid and j <= right:
if lst[i] < lst[j]:
tmp[pos] = lst[i]
i += 1
else:
tmp[pos] = lst[j]
j += 1
pos += 1
for k in range(i, mid + 1):
tmp[pos] = lst[k]
pos += 1
for k in range(j, right + 1):
tmp[pos] = lst[k]
pos += 1
lst[left:right + 1] = tmp[left:right + 1]
return lst
- Java
public class Solution {
public int[] mergeSort(int[] nums) {
int n = nums.length;
int[] tmp = new int[n];
merge(nums, tmp, 0, n - 1);
return nums;
}
private int[] merge(int[] nums, int[] tmp, int left, int right) {
if (left >= right) return null;
int mid = left + right >> 1;
merge(nums, tmp, left, mid);
merge(nums, tmp, mid + 1, right);
int i = left, j = mid + 1, pos = left;
while (i <= mid && j <= right) {
if (nums[i] < nums[j]) {
tmp[pos] = nums[i];
i++;
} else {
tmp[pos] = nums[j];
j++;
}
pos++;
}
for (int k = i; k < mid + 1; k++) {
tmp[pos] = nums[k];
pos++;
}
for (int k = j; k < right + 1; k++) {
tmp[pos] = nums[k];
pos++;
}
System.arraycopy(tmp, left, nums, left, right + 1 - left);
return nums;
}
}
题目变形：
148. 排序链表
面试题51. 数组中的逆序对
