排序算法总结以及c＋实现源码分享

排序算法是算法的基础，扎实掌握是一个合格程序员的内功，所以小编今天抽时间把排序算法总结一把，方便自己复习以及知识的分享。

一. 选择排序

1.算法思想

从头至尾扫描序列，找出最小的一个元素，和第一个元素交换，接着从剩下的元素中继续这种选择和交换方式，最终得到一个有序序列。

2.c++代码实现

#include

#include

#include

using namespace std;

template

void selectionSort(vector & arr) {

for (int i = 0; i < arr.size(); ++i) {

int minIndex = i;

for (int j = i + 1; j < arr.size(); ++j) {

if (arr[j] < arr[minIndex])

minIndex = j;

}

swap(arr[i], arr[minIndex]);

}

}

int main() {

vector arr{ 4,7,8,3,6,45 };

selectionSort(arr);

for (auto it = arr.begin(); it!= arr.end(); it++) {

cout

}

system("pause");

return 0;

}                                       

时间复杂度：O(N^2)

空间复杂度：O(1)

二. 插入排序

1.算法思想

插入排序是指在待排序的元素中，假设前面n-1(其中n>=2)个数已经是排好顺序的，现将第n个数插到前面已经排好的序列中，然后找到合适自己的位置，使得插入第n个数的这个序列也是排好顺序的。按照此法对所有元素进行插入，直到整个序列排为有序。

2.c++代码实现

#include

#include

#include

using namespace std;

template void insertSort(std::vector & arr) {

for (int i = 1; i < arr.size(); ++i) {

for (int j = i; j > 0; --j) {

if (arr[j] < arr[j - 1])

std::swap(arr[j], arr[j - 1]);

else

break;

}

}

}

int main() {

vector arr{ 4,7,8,3,6,45 };

selectionSort(arr);

for (auto it = arr.begin(); it != arr.end(); it++) {

cout

}

}

时间复杂度O(N^2)

空间复杂度：O(1)

应用场景：数组中大部分数据都是有序的。（排序日志）

三.快速排序

1.算法思想

该方法的基本思想是：

先从数列中取出一个数作为基准数。

分区过程，将比这个数大的数全放到它的右边，小于或等于它的数全放到它的左边。

再对左右区间重复第二步，直到各区间只有一个数。

2.c++代码实现

#include

#include

#include

using namespace std;

template int partition(std::vector& arr, int l, int r) {

T v = arr[l];

int j = l;

for (int i = l + 1; i

if (arr[i] < v) {

std::swap(arr[j + 1], arr[i]);

++j;

}

}

std::swap(arr[l], arr[j]);

return j;

}

template void quickSort(std::vector& arr,int l,int r) {

if (l >= r)

return;

int p = partition(arr, l, r);

quickSort(arr, l, p - 1);

quickSort(arr, p + 1, r);

}

template void quickSort(std::vector& arr) {

quickSort(arr, 0, arr.size() - 1);

}

int main() {

vector arr{ 4,7,8,3,6,45 };

quickSort(arr);

for (auto it = arr.begin(); it != arr.end(); it++) {

cout

}

}

了解IT相关内容，找“职坐标在线”