终于不用改论文了，希望文章大修顺利！

基础知识

排序算法的稳定性: 排序后值相同的前后位置不变

稳定的算法：

插入排序冒泡排序归并排序桶排序二叉树排序

不稳定的算法

选择排序希尔排序堆排序快速排序

内部排序：排序过程不涉及内、外存交换 外部排序：排序过程有内、外存交换

In-place sort（不占用额外内存或占用常数的内存）：插入排序、选择排序、冒泡排序、堆排序、快速排序。 Out-place sort：归并排序、计数排序、基数排序、桶排序。

---

快速排序

unstable sort、In-place sort 时间复杂度-> O(n2) (当输入数组已排序时) O(nlogn) “分而治之”的思想，一个序列中选一个值，把小于它的放左边，大于它的放右边。之后对左右两个子序列同样操作

代码： C

#include <stdio.h> #include <stdlib.h> int main(){ int a[] = {1,6,3,2,5}; quick_sort(a,0,5); int i = 0; for(i = 0;i < 5; i++){ printf("%d ", a[i]); } return 0; } void quick_sort(int s[], int l, int r){ if (l < r) { //Swap(s[l], s[(l + r) / 2]); //将中间的这个数和第一个数交换 int i = l, j = r, x = s[l]; while (i < j) { while(i < j && s[j] >= x) // 从右向左找第一个小于x的数 j--; if(i < j) s[i++] = s[j]; while(i < j && s[i] < x) // 从左向右找第一个大于等于x的数 i++; if(i < j) s[j--] = s[i]; } s[i] = x; quick_sort(s, l, i - 1); // 递归调用 quick_sort(s, i + 1, r); } }

Python

def quickSort(arr, left, right): if(left < right): print(arr) i, j = left, right if len(arr) <= 1: return flag = arr[left] while(left < right): while(left < right and arr[right] >= flag): right -= 1 if(left < right): arr[left] = arr[right] left += 1 while(left < right and arr[left] < flag): left += 1 if(left < right): arr[right] = arr[left] right -= 1 arr[right] = flag print(left, right, arr) quickSort(arr, i, right - 1) quickSort(arr, right + 1, j)

注意不能用切片的，因为切片传递的不是指针，切片是浅拷贝