插入排序 直接插入排序 从小到达排列,在第p
趟,将位置p
上的元素f(p)
与它之前的元素进行比较,f(p)
小则将之前的元素向后移动一位,直到找到合适的位置并插入
1 2 3 4 5 6 7 8 9 10 11 template <typename Object>void insertionSort (std::vector<Object> &x) { for (int p = 1 ; p < x.size (); ++p) { Object tmp = std::move (x[p]); int j; for (j = p; j > 0 && tmp < x[j - 1 ]; --j) x[j] = std::move (x[j - 1 ]); x[j] = std::move (tmp); } }
STL 中的插入排序
针对排序对象不是简单的整数,而是自定义的对象,因此需要特定的比较函数;同时一般用迭代器处理
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 template <typename Iterator, typename Comparator>void insertSort (const Iterator &begin, const Iterator &end, Comparator lessThan) { if (begin == end) return ; Iterator j; for (Iterator p = begin + 1 ; p != end; ++p) { auto tmp = std::move (*p); for (j = p; j != begin && lessThan (tmp, *(j - 1 )); --j) *j = std::move (*(j - 1 )); *j = std::move (tmp); } }
性能分析:
时间复杂度:
希尔排序 按照序列的下标,设置增量,根据增量对序列做增量分组,对每组使用直接插入排序;缩小增量重新做增量分组,使用直接插入排序;重复进行
1 2 3 4 5 6 7 8 9 10 11 12 13 template <typename Object>void shellSort (std::vector<Object> &x) { for (int gap = x.size () / 2 ; gap > 0 ; gap /= 2 ) for (int i = gap; i < x.size (); ++i) { Object tmp = std::move (x[i]); int j = i; for (; j >= gap && tmp < x[j - gap]; j -= gap) x[j] = std::move (x[j - gap]); x[j] = std::move (tmp); } }
性能分析:
最坏情况:
使用 Hibbard 增量优化后:
选择排序 选择排序 每n
趟在待排序元素中选取关键字最小的元素,并于序列中第n-1
个元素互换位置
1 2 3 4 5 6 7 8 9 10 11 12 13 template <typename Object>void selectSort (std::vector<Object> &x) { for (int i = 0 ; i < x.size () - 1 ; ++i) { int select = i; for (int j = i + 1 ; j < x.size (); ++j) if (x[j] < x[select]) select = j; if (select != i) std::swap (x[select], x[i]); } }
性能分析:
空间复杂度:
时间复杂度:
堆排序 每一趟在待排序元素中选取关键字最小/最大的元素加入有序子序列
通过优先队列 实现
通过构建一个小根堆,将待排序队列的元素依次插入小根堆中,根结点是最小的元素,且每次deleteMin
后,会自动调整小根堆,将现存的最小元素放入根结点
性能分析:
时间复杂度:
空间:为了构建这样的优先队列,成员函数array
的大小是略大于待排序数组的
交换排序 冒泡排序 重复走访需要排序的序列,按照升序交换相邻两个元素的位置,重复直至没有需要再交换的元素
1 2 3 4 5 6 7 8 template <typename Object>void BubbleSort (std::vector<Object> &x) { for (int i = 0 ; i < x.size () - 1 ; ++i) for (int j = 0 ; j < x.size () - 1 - i; ++j) if (x[j] > x[j + 1 ]) std::swap (x[j], x[j + 1 ]); }
性能分析:
时间复杂度:
快速排序 对待排序序列任意选取一项,则有小于所选项的一组、等于所选项的一组和大于所选项的一组;递归的将第一组和第三组排序,将这三组连接起来
如果序列中元素个数是 1 或 0,则返回
从序列中挑出一个元素(一般取中心位置的元素),称为枢纽元 (pivot)
重新排序序列,所有元素比枢纽元小的摆放在枢纽元前面,所有元素比枢纽元大的摆在枢纽元的后面(相同的数可以到任一边)。在这个分区退出之后,该枢纽元就处于数列的中间位置。这个称为分区(partition)操作
递归地(recursive)把小于枢纽元元素的子数列和大于枢纽元值元素的子序列排序
简单的递归排序算法
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 template <typename Object>void SORT (std::vector<Object> &items) { if (items.size () > 1 ) { std::vector<Object> smaller; std::vector<Object> same; std::vector<Object> larger; auto chosenItem = items[items.size () / 2 ]; for (auto i:items) { if (i < chosenItem) smaller.template emplace_back (std::move(i)) ; else if (i > chosenItem) larger.template emplace_back (std::move (i)); else same.template emplace_back (std::move (i)); } SORT (smaller); SORT (larger); std::move (std::begin (smaller), std::end (smaller), std::begin (items)); std::move (std::begin (same), std::end (same), std::begin (items) + smaller.size ()); std::move (std::begin (larger), std::end (larger), std::end (items) - larger.size ()); } }
实际的快速排序
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 template <typename Object>void quickSort (std::vector<Object> &x) { quickSort (x, 0 , x.size () - 1 ); } template <typename Object>const Object &median3 (std::vector<Object> &x, int left, int right) { int center = (left + right) / 2 ; if (x[center] < x[left]) std::swap (x[center], x[left]); if (x[right] < x[left]) std::swap (x[right], x[left]); if (x[right] < x[center]) std::move (x[right], x[center]); std::swap (x[center], x[right - 1 ]); return x[right - 1 ]; } template <typename Object>void quickSort (std::vector<Object> &x, int left, int right) { if (left + 10 <= right) { auto pivot = median3 (x, left, right); int i = left, j = right - 1 ; while (tr) { while (x[++i] < pivot) {} while (x[--j] > pivot) {} if (i < j) std::swap (x[i], x[j]); else break ; } std::swap (x[i], x[right - 1 ]); quickSort (x, left, i - 1 ); quickSort (x, i + 1 , right); } else insertSort (x, left, right) }
归并排序 建立在归并操作上的排序算法,通过合并两个已排序的序列到第三个空白序列来实现
申请空间,使其大小为两个已经排序序列之和,该空间用来存放合并后的序列
设定两个指针,最初位置分别为两个已经排序序列的起始位置
比较两个指针所指向的元素,选择相对小的元素放入到合并空间,并移动指针到下一位置
重复步骤 3 直到某一指针达到序列尾
将另一序列剩下的所有元素直接复制到合并序列尾
自顶向下递归,到底层以后,每个需要比较的序列只有一个元素,取其中较小的元素放入缓存序列后,然后复制另一个序列中的剩余元素,如此自底向上往复
每个需要比较的序列只有一个元素:从逻辑上看如此,实际上通过传参时的下标来标定被排序序列,划分出此阶段需要对比的两个序列
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 template <typename Object>void mergeSort (std::vector<Object> &x) { std::vector<Object> tmp (x.size()) ; mergeSort (x, tmp, 0 , x.size () - 1 ); } template <typename Object>void mergeSort (std::vector<Object> &x, std::vector<Object> &tmp, int left, int right) { if (left < right) { int center = (left + right) / 2 ; mergeSort (x, tmp, left, center); mergeSort (x, tmp, center + 1 , right); merge (x, tmp, left, center + 1 , right); } } template <typename Object>void merge (std::vector<Object> &x, std::vector<Object> &tmp, int leftPos, int rightPos, int rightEnd) { int leftEnd = rightPos - 1 ; int tmpPos = leftPos; int numElements = rightEnd - leftPos + 1 ; while (leftPos <= leftEnd && rightPos <= rightEnd) if (x[leftPos] <= x[rightPos]) tmp[tmpPos++] = std::move (x[leftPos++]); else tmp[tmpPos++] = std::move (x[rightPos++]); while (leftPos <= leftEnd) tmp[tmpPos++] = std::move (x[leftPos++]); while (rightPos <= rightEnd) tmp[tmpPos++] = std::move (x[rightPos++]); for (int i = 0 ; i < numElements; ++i, --rightEnd) x[rightEnd] = std::move (tmp[rightEnd]); }
性能分析:
时间复杂度:
计数排序 要求: 待排序序列的元素必须是具有确定范围的整数
找出待排序序列中最大和最小元素,计算差值并 +1 得到c
设置计数序列C
,长度为c
统计待排序序列中每个值为i
的元素的个数n
,并存入计数序列C
的第i
个位置
填充目标数组:将每组n
个值为i
的元素填充入目标数组
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 void countingSort (std::vector<int > &x) { int min = *std::min_element (x.cbegin (), x.cend ()); int max = *std::max_element (x.cbegin (), x.cend ()); int size = max - min + 1 ; std::vector<int > tmp (size) ; for (int i:x) tmp[i - min]++; x.clear (); for (int i = 0 ; i < size; ++i) { while (tmp[i]--) x.emplace_back (i + min); } }
性能分析:
时间复杂度:
桶排序 设置多个桶,利用映射关系,将符合条件的元素放入对应桶中,排序桶中元素和合并桶
尽可能将N
个元素均匀分配到K
个桶中
计数排序可以看作是每个桶只存储单一元素的桶排序
基数排序
将元素的数据按照位数切割成不同的数字
将个位做升序比较,放入对应桶中
完成后升序取出,放回序列
按十位做升序比较,放入对应桶中
完成后升序取出,放回序列
……
排序算法性能
数据结构性能