各类算法排序详解
程序员文章站
2024-03-17 22:08:22
...
归并排序 自带时间复杂度测试
//时间复杂度 O(N*log2N)
//稳定程度: 稳定
/*
确定分界点,中间位置
两端排序
归并,合二为一
*/
#include<iostream>
#include<time.h>
using namespace std;
int tmp[250001];
void Sort(int List[], int l, int r);
int main()
{
int a[250000];
int k, j;
// 设置种子
srand((unsigned)time(NULL));
/* 生成 10 个随机数 */
for (k = 0; k < 250000; k++)
{
// 生成实际的随机数
j = rand();
a[k] = j;
}
clock_t start_time = clock();
Sort(a,0,250000-1);
clock_t end_time = clock();
//for (int i = 0; i < 200000; i++)
//{
// cout << a[i] << " ";
//}
cout << "\n程序段运行时间:" << static_cast<double> (end_time - start_time) / CLOCKS_PER_SEC * 1000 << "ms" << endl;
system("pause");
}
void Sort(int List[], int l, int r)
{
if (l >= r) return;
int mid = l + r >> 1; //取中间数
Sort(List, l, mid), Sort(List, mid + 1, r); //左右递归排序
int k = 0, i = l, j = mid + 1; //k表示已合并数组中有几个元素,分开两个有序数组
while (i <= mid && j <= r) //进行双指针比较
if (List[i] <= List[j]) tmp[k++] = List[i++];
else tmp[k++] = List[j++];
while (i <= mid) tmp[k++] = List[i++]; //分别处理剩余部分
while (j <= r) tmp[k++] = List[j++];
for (i = l, j = 0; i <= r; i++, j++) List[i] = tmp[j]; //拷入原空间
}
快速排序 自带时间复杂度检测
//时间复杂度 O(N*log2N
//稳定性:不稳定
//来源于分治思想
/*
确定分界点
调整区间
递归处理两端
算法思想,快排是基于冒泡排序的优化,冒泡排序从一侧开始进行,而快排是两边同时进行从而时间复杂度折半,同时包含了二分的思想在里面
*/
#include<iostream>
#include<time.h>
using namespace std;
void Sort(int List[], int l, int r);
int main()
{
int a[80000];
int k, j;
// 设置种子
srand((unsigned)time(NULL));
/* 生成 10 个随机数 */
for (k = 0; k < 80000; k++)
{
// 生成实际的随机数
j = rand();
a[k] = j;
}
clock_t start_time = clock();
Sort(a,0,80000-1);
clock_t end_time = clock();
for (int i = 0; i < 80000; i++)
{
cout << a[i] << " ";
}
cout << "\n程序段运行时间:" << static_cast<double> (end_time - start_time) / CLOCKS_PER_SEC * 1000 << "ms" << endl;
system("pause");
}
void Sort(int List[], int l, int r)
{
if (l >= r) return; //边界判断
int i = l - 1, j = r + 1, x = List[l]; //x为分界点
while (i < j)
{
//两次do,主要在于找到左右两侧<x和>x的第一个数
do i++; while (List[i] < x);
do j--; while (List[j] > x);
if (i < j) swap(List[i], List[j]);
else break;
}
Sort(List, l, j), Sort(List, j + 1, r);
}
冒泡排序 自带时间复杂度测试
#include<iostream>
#include<time.h>
using namespace std;
void Sort(int List[], int n);
int main()
{
int a[10000];
int k, j;
// 设置种子
srand((unsigned)time(NULL));
/* 生成 10 个随机数 */
for (k = 0; k < 10000; k++)
{
// 生成实际的随机数
j = rand();
a[k] = j;
}
clock_t start_time = clock();
Sort(a, 10000);
clock_t end_time = clock();
for (int i = 0; i < 10000; i++)
{
cout << a[i] << " ";
}
cout << "\n程序段运行时间:" << static_cast<double> (end_time - start_time) / CLOCKS_PER_SEC * 1000 << "ms" << endl;
system("pause");
}
void Sort(int List[], int n)
{
for (int i = 0; i < n - 1; i++)
{
for (int j = 0; j < n - i - 1; j++) //j<n-i-1:首先j不与自己比较所以-1,其次每次外循环都会产生一个已经排序的最大数,所以内循环要排除已经排好的,即总数为n-i。
if (List[j] > List[j + 1])
swap(List[j], List[j + 1]);
}
}
选择排序 自带时间复杂度分析
从当前未排序的整数中找到最小的整数,将它放在已排序的整数列表的最后。
#include<iostream>
#include<time.h>
using namespace std;
void Sort(int List[], int n);
int main()
{
int a[10000];
int k, j;
// 设置种子
srand((unsigned)time(NULL));
/* 生成 10 个随机数 */
for (k = 0; k < 10000; k++)
{
// 生成实际的随机数
j = rand();
a[k] = j;
}
clock_t start_time = clock();
Sort(a, 10000);
clock_t end_time = clock();
for (int i = 0; i < 10000; i++)
{
cout << a[i] << " ";
}
cout << "\n程序段运行时间:" << static_cast<double> (end_time - start_time) / CLOCKS_PER_SEC * 1000 << "ms" << endl;
system("pause");
}
void Sort(int List[], int n)
{
for (int i = 0; i < n - 1; i++)
{
int min = i;//min处,假设第一个是最小的,是;数组的下标
for (int j = i + 1; j < n; j++) //j=i+1是因为之前已经扫描过了
{
if (List[j] < List[min])
{
min = j; //移动记录下来
}
}
swap(List[i], List[min]); //扫描一遍结束后,交换一次
}
}
选择排序与冒泡排序的区别
冒泡排序:
冒泡排序(BubbleSort)的基本概念是:依次比较相邻的两个数,将小数放在前面,大数放在后面。即在第一趟:首先比较第1个和第2个数,将小数放前,大数 放后。
然后比较第2个数和第3个数,将小数放前,大数放后,如此继续,直至比较最后两个数,将小数放前,大数放后。至此第一趟结束,将最大的数放到了最后。
在第二趟:仍从第一对数开始比较(因为可能由于第2个数和第3个数的交换,使得第1个数不再小于第2个数),将小数放前中,大数放后,一直比较到倒数第二个数(倒数第一的位置上已经是最大的),第二趟结束,在倒数第二的位置上得到一个新的最大数(其实在整个数列中是第二大的数)。如此下去,重复以上过程,直至最终完成排序。
选择排序
第一次从下标为0的开始下标为0的这个数与后面的n-1个进行比较;找出最小或者最大的放在下标为0的这个位置;第二次从下标为1的开始比较;查询剩下的最大或者最小值;放在下标为1的位置;以此类推;直到排序完成。
总结
从上两段代码可以看出,它们处于同一个数量级,即时间复杂度是相同的,都用了两层循环,为O(n^2)(n:排序个数); 但是内层循环中,冒泡排序的互换位置的操作从概率上讲要明显多于选择排序. 整个排序算法,选择排序换位操作为O(n),冒泡排序为O(n^2/2). 所以综合来讲选择排序的时间效率要高于冒泡排序.