####排序算法
一、插入排序
（1）算法思想（以升序举例）：
对于一个已经有序的序列，又来一个数x，从倒数第一个数进行比较，如果x比这个数小，这个数就往后挪。
（2）代码实现
//O(N)最好顺序-O(N*N)最坏逆序
void insert_sort(int*a, int n)
{
for (int i = 0; i = 0)
{
if (a[end] > x)
{
a[end+1] = a[end];
--end;
}
else
{
break;
}
}
a[end + 1] = x;
}
}（3）改进：希尔排序
思想：插入排序在整体有序的情况下效果最好，于是希尔排序先预排序让序列先大体有序，最后进行插入排序来取得最好的效果。它的时间复杂度大概为O(N^1.3)。
步骤：把数字分成gap个一组->对每组数据进行插入排序来达到大体有序的目的->对全体插入排序
//gap越小，越接近有序。pow(n,1.3)
void shell_sort(int* a, int n)
{
int gap = n;
while (gap > 1)
{
gap = gap/3 + 1;//gap>1都是预排序，gap==1为直接插入排序
for (int i = 0; i = 0)
{
if (a[end] > x)
{
a[end + gap] = a[end];
end -= gap;
}
else
{
break;
}
}
a[end + gap] = x;
}
}
}
}二、选择排序
思想：在序列中每次都找到最小值和最大值，把它们放在应该的位置。
//O(N*N)
void select_sort(int* a, int n)
{
//assert(a);
int begin = 0, end = n - 1;
while (begin a[max_])max_ = i;
}
swap(&a[begin], &a[min_]);
if (max_ == begin)
{
max_ = min_;
}
swap(&a[end], &a[max_]);
++begin;
--end;
}
}三、堆排序
思想：使用堆的down操作来找到大堆中的最大值，把它交换到尾部，再对a[0]进行一个down。
//nlogn
void heap_sort(int* a, int n)
{
for (int i = (n - 2) / 2; i >= 0; --i)
{
heap_down(a, n, i);
}
int end = n - 1;
while (end > 0)
{
swap(&a[0], &a[end]);
heap_down(a, end, 0);
--end;
}
}四、冒泡排序
思想：每次循环都确定一个最大值，先是最大的，放到尾部，其次是第二大的，直到没有发生交换，说明排序已经完成。
//O(n*n) 最好:n,遍历一次就知道结果
void bubble_sort(int* a, int n)
{
for (int i = 0; i a[j+1])
{
f = 1;
swap(&a[j], &a[j+1]);
}
}
if (f == 0)
{
break;
}
}
}五、快速排序
(1)思想：每次排序找一个key，经过排序使得序列的左边数据都=key，递归处理。
void quick_sort(int* a, int begin, int end)
{
if (begin >= end)
return;
int keyi = quick1_sort(a, begin, end);
quick1_sort(a + begin, begin, keyi - 1);
quick1_sort(a + begin, keyi + 1, end);
}
//传统写法：选择一个key，右边先走，左边再走，交换，直到l==r
int quick1_sort(int* a, int begin, int end)
{
int l = begin;
int r = end;
int keyi = a[l];
while (l = a[keyi])
{
r--;
}
//现在的a[r]= key)
{
r--;
}
a[pit] = a[r];
pit = r;//这是新的坑
while (l 在传统写法中，左边作key，为什么让右边先走？
为了保证找到的相遇的位置一定是r一直往左边走，直到遇到l，说明这个位置右边的值都比Key大，相遇的位置是l上一轮停下来的，这里要么是key（第一轮），要么比key小（不是第一轮了，上一轮r换过去的），时间复杂度为nlogn。
(2)优化
思想1：当key每次都是最大或者最小时复杂度最高，选择一个值在中间的数才能有好的结果。
//优化1=key每次都是最小或者最大效果最差：有序或者接近有序->1.随机选Key 2.三数选中
int get_key(int* a, int begin, int end)//得到下标
{
int mid = (begin + end) / 2;
if (a[begin] a[begin])return begin;
else if (a[mid] 思想2：当递归区间比较小的时候，不再递归处理，而是用其他算法对小区间排序，这样可以大大减少递归的次数（80%）
void quick_sort(int* a, int begin, int end)
{
if (begin >= end)return;
if (end - begin > 10)//80%
{
int keyi = quick1_sort(a, begin, end);
quick1_sort(a + begin, begin, keyi - 1);
quick1_sort(a + begin, keyi + 1, end);
}
else
{
insert_sort(a,end -begin+1 );
}
}(3)快拍的非递归写法
递归转非递归的方法：1.直接改循环。2.使用栈来模拟（这样不用担心栈溢出，因为堆的空间比较大）
void quick_sort_nor(int* a, int begin, int end)
{
stackst;
st.push(end);
st.push(begin);
while ()
{
int l = st.top();
st.pop();
int r = st.top();
st.pop();
//(l,key-i-1)(keyi+1,r)
int keyi = quick1_sort(a, l, r);
if (r > keyi + 1)
{
st.push(r);
st.push(keyi + 1);
}
if (l 六、归并排序
（1）思想：先把序列递归分成小区间，再把小区间排成有序，接着把已经有序的小区间进一步变成有序的区间。
void merge_sort(int* a, int n)
{
int* temp = (int*)malloc(sizeof(int) * n);
if (temp == NULL)
{
exit(-1);
}
_merge_sort(a, 0, n - 1, temp);
free(temp);
}
void _merge_sort(int* a, int begin, int end, int* temp)
{
if (begin >= end)return;
int mid = (begin + end) / 2;
_merge_sort(a, begin, mid, temp);
_merge_sort(a, mid+1, end, temp);
//归并，使小区间有序
int begin1 = begin, end1 = mid,
begin2 = mid + 1, end2 = end;
int i = begin;
while (begin1 (2)非递归写法
思想：把数组分成1个一组，2个一组……对每两个小组进行归并合成一个大的组。要注意边界问题。
对[i, i+gap-1]和[i+gap, i+2gap-1]归并；[i+2gap, i+3gap-1]和[i+3gap, i+4gap-1]归并……
void merge_sort_nor(int* a, int n)
{
int* temp = (int*)malloc(sizeof(int) * n);
if (temp == NULL)
{
exit(-1);
}
int gap = 1;
while (gap= n)
{
end1 = n - 1;
//修正成不存在的区间
begin2 = n;
end2 = n - 1;
}
else if (begin2 >= n)
{
begin2 = n;
end2 = n - 1;
}
else if (end2 >= n)
{
end2 = n - 1;
}
j = i;
while (begin1 七、相关概念
1.稳定性：相对顺序不变。eg: 1 2 3 3 4 2，在排序之后，2的相对顺序不变，5的相对顺序不变。
2.内排序：在内存上进行的排序
外排序：在磁盘上进行的排序
eg.有10亿个int整数，需要4G的空间，对这些数字排序。思想：为了提高速度，先把这些数字分成四份，把每一份放在内存里面归并排序再写入文件，之后对这些文件进行归并排序。（fprintf/fscanf)。
八、各个内排序算法比较
服务器托管，北京服务器托管，服务器租用 http://www.fwqtg.net
目录 一.什么是mybatis mybatis的概念 mybatis的优势 二.mybatis相对于JDBC，框架帮我们做了哪些事情？ 三.对包含mybatis的程序进行实操 1.创建项目 2.修改配置文件 3.准备数据库相关内容 4.准备对应的xml文件和对…
