排序

1.插入排序：

源码一：

void InsertSort(vector<int>&arr)
{
int n = arr.size();
for (int i = 0; i < n - 1; ++i)
{
//记录有序序列最后一个元素的下标
int end = i;
//待插入的元素
int tem = arr[end + 1];
//单趟排
while (end >= 0)
{
//比插入的数大就向后移
if (tem < arr[end])
{
arr[end + 1] = arr[end];
end--;
}
//比插入的数小，跳出循环
else
{
break;
}
}
//tem放到比插入的数小的数的后面
arr[end + 1] = tem;
//代码执行到此位置有两种情况:
//1.待插入元素找到应插入位置（break跳出循环到此）
//2.待插入元素比当前有序序列中的所有元素都小（while循环结束后到此）
}
}

源码二：

void charu(vector<int>&a)
{
if (a.size() <= 1)
return ;
for (int i = 1;i<a.size(); i++)
{
int k = i - 1;
while (k>= 0&&a[i]<a[k])
{
k--;
}
a.insert(a.begin()+(k+1),a[i]);
a.erase(a.begin() + i+1);
}
}

2.快排

void quicksort(vector<int>&a,int begin,int end)
{
if (begin >= end)
return;
int l = begin;
int r = end;
int key=begin;
while (l!=r)
{
while (r>l&&a[r] >= a[key])
{
r--;
}
while (r>l&&a[l] <=a[key])
{
l++;
}
swap(a[l], a[r]);
}
swap(a[key], a[l]);
key = l;
quicksort(a, begin, key- 1);
quicksort(a,key+1,end);
}

插入排序优点：原地排序，时间复杂度最好为O(n),最坏为O(n^2),传统方法中，最好情况的就是基本有序，此时为O(n),最坏情况为基本逆序，此时时间复杂度为O(n^2)

快速排序：原地排序，时间复杂度为O(nlogn),若数组基本有序或者基本逆序，此时并不适合快排，当数组基本无序时适合快排。