归并排序：
完整代码：
空间复杂度O（N）
时间复杂度O（NlogN）
每一层归并的时间复杂度为O（N）
归并层数最大为O（logN+1）
#include<iostream>
using namespace std;
#include<vector>
#include<set>
#include <unordered_set>
#include<stack>
//合并
void merge(int a[], int temparr[], int left, int mid, int right)
{
int l_pos = left;
int r_pos = mid + 1;
int t_pos = left;
while (l_pos <= mid && r_pos <= right)
{
if(a[l_pos] < a[r_pos])
{
temparr[t_pos++] = a[l_pos++];
}
else
{
temparr[t_pos++] = a[r_pos++];
}
}
while (l_pos <= mid)
{
temparr[t_pos++] = a[l_pos++];
}
while (r_pos <= right)
{
temparr[t_pos++] = a[r_pos++];
}
//拷贝元素
while (left <= right)
{
a[left] = temparr[left];
left++;
}
}
//归并排序
void msort(int a[],int temparr[],int left,int right)
{
if (left < right)
{
/*
如果只有一个元素 那么就不需要继续划分
只有一个元素的区域本身就是有序的 只需要合并即可
*/
//int mid = (right + left ) / 2;
int mid = (right - left) / 2 + left; //加left预防数据溢出
//左半区
msort(a, temparr, left, mid);
//右半区
msort(a, temparr, mid+1, right);
//合并
merge(a, temparr, left, mid, right);
}
}
归并排序入口
//void merge_sort(int a[], int n)
//{
// //定义一个辅助数组
// int* temparr = (int * )malloc (n * sizeof(int));
// //辅助数组空间开辟成功
// if (temparr)
// {
// msort(a, temparr, 0, n - 1);
// free (temparr);
// }
// else
// {
// cout << "无法开辟空间" << endl;
// }
//
//}
//归并排序入口
void merge_sort(int a[], int n)
{
//定义一个辅助数组
int* temparr = new int [n * sizeof(int)];
//辅助数组空间开辟成功
if (temparr)
{
msort(a, temparr, 0, n - 1);
delete[] temparr;
}
else
{
cout << "无法开辟空间" << endl;
}
}
int main()
{
int a[] = { 2,3,8,1,4,9,10,7,16,14 };
int len = sizeof(a) / sizeof(a[0]);
cout << "排序前 " << endl;
for (int i = 0; i < len; i++)
{
cout << a[i] << " ";
}
cout << endl;
merge_sort(a, len);
cout << "排序后 " << endl;
for (int i = 0; i < len; i++)
{
cout << a[i] << " ";
}
cout << endl;
}
快速排序：
时间复杂度：O（NlogN）
空间复杂度：O（NlogN）
划分的实现：
把小的放到前面去
#include<iostream>
using namespace std;
#include<vector>
#include<set>
#include <unordered_set>
#include<stack>
//划分中间
int partition(int a[], int low, int hight)
{
int point = a[hight];
int i = low;
for (int j = low; j < hight; ++j)
{
if (a[j] < point)
{
swap(a[j], a[i++]);
}
}
swap(a[hight], a[i]);
return i;
}
//递归划分
void m_qsort(int a[], int low,int hight)
{
if (low < hight)
{
int mid = partition(a,low,hight);
m_qsort(a,low, mid - 1);
m_qsort(a, mid + 1, hight);
}
}
//快速排序入口
void quick_sort(int a[], int len)
{
m_qsort(a, 0,len - 1);
}
int main()
{
/*int a[] = { 2,3,8,1,4,9,10,7,16,14 };*/
int a[] = { 3,1,2,4,5 };
int len = sizeof(a) / sizeof(a[0]);
cout << "排序前 " << endl;
for (int i = 0; i < len; i++)
{
cout << a[i] << " ";
}
cout << endl;
quick_sort(a, len);
cout << "排序后 " << endl;
for (int i = 0; i < len; i++)
{
cout << a[i] << " ";
}
cout << endl;
}
希尔排序：
时间复杂度：
希尔排序时间复杂度依赖于增量序列
除了一些简单的序列 其他序列的复杂度证明是未解决的问题
最坏的情况：O（N2）
代码实现：
#include<iostream>
using namespace std;
#include<vector>
#include<set>
#include <unordered_set>
#include<stack>
//希尔排序
void shell_sotr(int arr[], int len)
{
int i, j, inc, key;
for (inc = len / 2; inc > 0; inc /= 2)
{
for (i = inc; i < len; i++)
{
key = arr[i];
for (j = i; j >= inc && key < arr[j - inc]; j--)
{
arr[j] = arr[j - inc];
}
arr[j] = key;
}
}
}
int main()
{
int a[] = { 2,3,8,1,4,9,10,7,16,14 };
int len = sizeof(a) / sizeof(a[0]);
cout << "排序前 " << endl;
for (int i = 0; i < len; i++)
{
cout << a[i] << " ";
}
cout << endl;
shell_sotr(a, len);
cout << "排序后 " << endl;
for (int i = 0; i < len; i++)
{
cout << a[i] << " ";
}
cout << endl;
}
冒泡排序：
时间复杂度：
平均、最坏：O（N2）
最好：O（N）
代码实现：
#include<iostream>
using namespace std;
//冒泡排序
void bubble_sotr(int arr[], int len)
{
int i, j;
for (i = 0; i < len - 1; i++)
{
for (int j = 0; j < len - i - 1; j++)
{
if (arr[j] > arr[j + 1])
{
int temp = arr[j + 1];
arr[j + 1] = arr[j];
arr[j] = temp;
}
}
}
}
int main()
{
int a[] = { 2,3,8,1,4,9,10,7,16,14 };
int len = sizeof(a) / sizeof(a[0]);
cout << "排序前 " << endl;
for (int i = 0; i < len; i++)
{
cout << a[i] << " ";
}
cout << endl;
bubble_sotr(a, len);
cout << "排序后 " << endl;
for (int i = 0; i < len; i++)
{
cout << a[i] << " ";
}
cout << endl;
}
插入排序：
时间复杂度：
平均、最坏：O（N2）
最好：O（N）
代码实现：
//插入排序
void insert_sotr(int arr[], int len)
{
int i, j;
for (i = 1; i < len ; ++i)
{
for (j = i; j > 0; --j)
{
if (arr[j] < arr[j - 1])
{
int temp = arr[j - 1];
arr[j - 1] = arr[j];
arr[j] = temp;
}
}
}
}
选择排序：
时间复杂度：
O（N2）
代码实现：
//选择排序
void select_sort(int a[], int len)
{
for (int i = 0; i < len; ++i)
{
int min = i;
for (int j = i + 1; j < len; j++)
{
if (a[j] < a[min])
{
min = j;
}
}
int temp = a[i];
a[i] = a[min];
a[min] = temp;
}
}
堆排序在面试题那篇文章之中！
|