文章目录
不啰嗦,直接上图:
相邻两个数两两相比,n[i]跟n[j+1]比,如果n[i]>n[j+1],则将两个数进行交换
复杂度分析: 在一般情况下,每一个数都要与之后的数进行匹配,所以匹配次数将与数据量n挂钩,又由于每轮匹配都要进行(n-1)次比较,所以平均时间复杂度为O(n^2)。
当然,可以对冒泡排序进行优化,比方说可以设置一个标志位,当哪次匹配没有发生数据交换时,就不用再进行后面的匹配了。 还可以做个优化,纪录下数据尾部已经稳定下的部分,比如说倒数八个数字已经稳定,那么匹配到倒数第九个数,只要和倒八匹配一下即可知道要不要往后继续匹配。
不过,冒泡排序一般也不会用在大数排序上,所以嘛,老老实实的把基础代码写好比较重要。
这些天做题的时候吃了不少 快速排序不熟的亏,我痛下决心,一定要自己写出快速排序的几种实现方法!
快速排序是很重要的算法,和傅里叶变化等算法并称二十世纪最伟大的十大算法。
快速排序的核心思维就是“分而治之”,就像封建王朝的“分封制”。将一大块“领土”,依据“嫡庶长幼”,分为不同部分,各个部分在自行细分,直到分无可分之后,便等级森严了。
说白点,就是在序列中找个元素充当中间量,大的往后,小的往前,一分为二,二分为四,四分为八···
那么,快速排序的技术核心,便呼之欲出了。其一就是这个中间量怎么找,其二就是怎么移动各个元素。
这个元素的选择啊,并不是说要遵循什么准则,你可以选序列头,序列尾,序列中间元素,都可以。 不过选完之后把基准元素放到序列头的位置。
为了简单,后面我就直接选首元素了。
这个方法呢,如果对快慢指针和双指针不是很了解的朋友可以现在了解一下。
首先啊,确定基准为4,左指针指向第一个元素,右指针指向尾巴。
左指针开始,向前遍历,找到第一个大于基准的元素就停下,轮到右指针,同理。
当两个指针都停下之后,将两个指针所指向的值互换位置。
重复上述步骤直到左右指针重合。
重合之后,将基准元素与左右指针当前位置元素进行互换。
一次循环之后,重复上述动作,对划分出的部分再次循环,直到每个部分都只有一个元素为止。
这个是快慢指针实现。
这个mark,是慢指针。快指针没标出来。,依旧找好了基准,快指针从慢指针后一位开始快速遍历,直到遍历到小于基准元素的元素时停滞。
将慢指针前移一位,将当前快慢指针位置元素互换(如果重叠就算了)。然后快指针继续向后走。
重复上述步骤直到左右指针重合。
重合之后,将基准元素与左右指针当前位置元素进行互换。
一次循环之后,重复上述动作,对划分出的部分再次循环,直到每个部分都只有一个元素为止。
大数排序,至少也要用快速排序。
这个动画已经够明确了吧。
复杂度分析
时间复杂度:插入算法,就是保证前面的序列是有序的,只需要把当前数插入前面的某一个位置即可。 所以如果数组本来就是有序的,则数组的最好情况下时间复杂度为O(n)。 如果数组恰好是倒=倒序,比如原始数组是5 4 3 2 1,想要排成从小到大,则每一趟前面的数都要往后移,一共要执行n-1 + n-2 + … + 2 + 1 = n * (n-1) / 2 = 0.5 * n2 - 0.5 * n次,去掉低次幂及系数,所以最坏情况下时间复杂度为O(n2)
平均时间复杂度(n+n2 )/2,所以平均时间复杂度为O(n2)
空间复杂度:插入排序算法,只需要两个变量暂存当前数,以及下标,与n的大小无关,所以空间复杂度为:O(1)
希尔排序是把记录按下标的一定增量分组,对每组使用直接插入排序算法排序;随着增量逐渐减少,每组包含的关键词越来越多,当增量减至1时,整个文件恰被分成一组,算法便终止。
这个步长可以好好考虑一下要设多大,一般取三分之一表长就好了。
复杂度分析
经大量人研究,希尔排序的平均时间复杂度为O(n^1.3)(这个我也不知道咋来的,书上和博客上都这样说,也没找到个具体的依据)。
复杂度分析
其实这个我也没看太懂。。 我觉得还不如直接构造成二叉搜索树,然后前序遍历。
堆排序的基本思想是:将待排序序列构造成一个大顶堆,此时,整个序列的最大值就是堆顶的根节点。将其与末尾元素进行交换,此时末尾就为最大值。然后将剩余n-1个元素重新构造成一个堆,这样会得到n个元素的次小值。如此反复执行,便能得到一个有序序列了
复杂度分析
无论原始数组是否是有序的,都要递归分隔并向上归并排序,所以时间复杂度始终是O(nlog2n)
每次两个数组进行归并排序的时候,都会利用一个长度为n的数组作为辅助数组用于保存合并序列,所以空间复杂度为O(n)
这个图也挺有趣啊。
假如待排数据可以分为d个关键字,则基数排序的时间复杂度将是O(d*2n) ,当然d要远远小于n,因此基本上还是线性级别的。
系数2可以省略,且无论数组是否有序,都需要从个位排到最大位数,所以时间复杂度始终为O(d*n) 。其中,n是数组长度,d是最大位数。
#include<vector>
#include<iostream>
using namespace std;
void bulu(vector<int>& vec) {
int sz = vec.size();
if (sz == 0)
return;
int temp = 0;
int continue_flag = 1;
while (continue_flag) {
for (int i = 0, j = 1; j < sz; i++, j++) {
continue_flag = 0;
if (vec[i] > vec[j]) {
temp = vec[i];
vec[i] = vec[j];
vec[j] = temp;
continue_flag = 1;
}
}
}
}
int main()
{
vector<int> test = { 2,5,1,5,3,7,5,7,5,6 };
bulu(test);
for (int i = 0; i < 10; i++) {
cout << test[i] << " ";
}
return 0;
}
以下代码现场手写,如果有什么纰漏还望不吝赐教。
不好意思一段简单代码写了一晚上,不过我已经初步测试好了。
如果有要测试/调试的朋友,我可以讲一下我的调试思路:
先对两个数据进行一次调试,因为这是最后一道坎,这个要是有问题,后面都是白费。 然后·对三个数据进行测试,相信有了前面的基础这个测试会比较顺利。 然后四个数据,五个数据,越来越顺利。我测到六个数据之后便不再测试了,看它没什么情况发生。
如果你有兴趣,建议你去拿其他人的代码测试,他们是把递归和归并分开的,反正我用了几个别人的代码来测试,全崩了。
#include<iostream>
#include<vector>
using namespace std;
void doubleSideSort(vector<int> &vec1,int left,int right) //序列与左右指针传入
{
//结束语
if (right == left)
return;
//基准确定
int flag = vec1[left];
int keep_right = right;
int keep_left = left;
int change_temp;
//当左右指针还没重合
while (left<right)
{
//左指针先走
while (left<right && vec1[left]<=flag)
{
left++;
}//当遇到比基准大的数,停下来
//轮到右指针走
while (left < right && vec1[right] >= flag) //可以都等,反正最后都会归并
{
right--;
}//当遇到比基准小的数,停下来
if (left < right)
{
change_temp = vec1[left];
vec1[left] = vec1[right];
vec1[right] = change_temp;
}
//然后继续循环
}
//left--;
//接着将基准放进去,此时必定是左右相合,则左值若大于左值左边一位,和左值左边一位换,若小,则和左值换
if (vec1[left] > vec1[left - 1])
{
vec1[keep_left] = vec1[left-1];
vec1[left-1] = flag;
}
else
{
vec1[keep_left] = vec1[left];
vec1[left] = flag;
}
doubleSideSort(vec1,0,left-1);
doubleSideSort(vec1, right, keep_right);
}
int main()
{
vector<int> vec1 = { 4,6,8,7,9,3,1}; //测试用2个数测试最直观,因为最后都要通过这一步才能正常
int left = 0;
int right = vec1.size() - 1;
doubleSideSort(vec1, left, right);
for (; left <= right; left++)
cout << vec1[left] << " ";
cout << endl;
return 0;
}
快慢指针我还是比较有信心的,所以我就测试了四组数据。 如果有任何问题,欢迎留言。
void oneSideSort(vector<int>& vec1, int slow, int hight)
{
//设置退出条件
if (slow >= hight)
return;
//将标志位留住
int flag = vec1[slow];
int keep_slow = slow;
int keep_hight = hight;
//使用快指针遍历,将小于标志位的前移
for (int quick = slow + 1; quick <= hight; quick++)
{
if (vec1[quick] < flag)
{
slow++;
int change_temp = vec1[slow];
vec1[slow] = vec1[quick];
vec1[quick] = change_temp;
}
}
vec1[keep_slow] = vec1[slow];
vec1[slow] = flag;
oneSideSort(vec1, keep_slow,slow-1);
oneSideSort(vec1,slow+1, keep_hight);
}
int main()
{
vector<int> vec1 = {2,1,2,3}; //测试用2个数测试最直观,因为最后都要通过这一步才能正常
int left = 0;
int right = vec1.size() - 1;
oneSideSort(vec1, left, right);
for (; left <= right; left++)
cout << vec1[left] << " ";
cout << endl;
return 0;
}
#include<iostream>
#include<cstdlib>
using namespace std;
//交换数组元素位置位置
void swap(int& a, int& b)
{
int temp = a;
a = b;
b = temp;
}
/*
插入排序。注意,若后面一个元素比其前面一个元素小,则将这两个元素交换位置,然后再来比较这个插入元素与前面一个元素的大小,若小,则还需要交换这两个元素位置,一直到这个插入元素在正确的位置为止
*/
void insertSort(int a[], int length)
{
for (int i = 1; i < length; i++)
{
for (int j = i - 1; j >= 0 && a[j + 1] < a[j]; j--)
{
swap(a[j], a[j + 1]);
}
}
}
int main()
{
int a[] = { 2,1,4,5,3,8,7,9,0,6 };
insertSort(a, 10);
for (int i = 0; i < 10; i++)
{
cout << a[i] << " ";
}
cout << endl;
system("pause");
return 0;
}
int shellSort(int* shell,int ishell)
{
int step,i,temp;
step = ishell/3+1; // 设定步长
for( ; step>0 ;)
{
for(i=0 ; i+step<ishell ; )
{
if(shell[i] > shell[i+step])
{
temp = shell[i];
shell[i] = shell[i+step];
shell[i+step] = temp;
}
i++;
}
step--;
}
}
void SelectSort(int* select,int lenth)
{
int i,j,temp,min;
for(i = 0;i<lenth;i++)
{
min = i;
for(j = i+1;j<lenth;j++)
{
if(select[i]>select[j])
{
min = j;
}
}
if(min != i)
{
temp = select[i];
select[i] = select[min];
select[min] = temp;
}
}
}
#include<iostream>
using namespace std;
void merge(int arr[], int L, int R, int M)
{
int LEFT_SIZE = M - L;
int RIGHT_SIZE = R - M + 1;
int* L_arr = new int [LEFT_SIZE];
int* R_arr = new int[RIGHT_SIZE];
int i,j,k;
//将左边数组的值赋值给新数组
for (i = L; i < M; i++)
{
L_arr[i - L] = arr[i];
}
//将右边数组的值赋值给新数组
for (i = M; i <= R; i++)
{
R_arr[i - M] = arr[i];
}
i = 0, j = 0, k = L;
//左右数组同时比较
while (i < LEFT_SIZE && j < RIGHT_SIZE)
{
if (L_arr[i] < R_arr[j])
{
arr[k] = L_arr[i];
i++;
k++;
}
else
{
arr[k] = R_arr[j];
j++;
k++;
}
}
while (i < LEFT_SIZE)
{
arr[k] = L_arr[i];
i++;
k++;
}
while (j < RIGHT_SIZE)
{
arr[k] = R_arr[j];
j++;
k++;
}
}
void mergeSort(int arr[], int L, int R)
{
if (L == R)
{
return;
}
int M = (L + R) / 2;
mergeSort(arr, L, M);
mergeSort(arr, M+1, R);
merge(arr, L,R,M+1);
}
int main()
{
int arr[] = { 2,8,23,10,4,1,6,7 };
int L = 0;
int R = 7;
int M = 4;
//merge(arr, L, R, M);
mergeSort(arr, L, R);
for (int i = 0; i <= R; i++)
{
cout << arr[i] << endl;
}
return 0;
}
/*算法:基数排序*/
#include <iostream>
using namespace std;
bool rxsort(int A[],int l,int h,int d,int k){
if(NULL==A||l>h)
return false;
int size = h-l+1;
int* counts = new int[k];//用于计数排序的辅助数据,详见计数排序
int* temp = new int[size];//用于存储重新排序的数组
int index;
int pval=1;
//依次处理不同的位
for(int i=0;i<d;i++){
//counts数组清零
for(int j=0;j<k;j++)
counts[j] = 0;
for(int j=l;j<=h;j++){
/*
1.data[j]/pval:去掉数字data[j]的后i个数,例如:
当data[j]=1234,i=2时,此时pval=100,data[j]/pval=12;
2.(data[j]/pval)%k:取数字data[j]/pval的最后一位数
3.(int)(data[j]/pval)%k:取数字data[j]的第i位数
*/
index = (int)(A[j]/pval)%k;
/*
统计数组A中每个数字的第i位数中各个数字的频数,用于计数排序;
*/
counts[index]++;
}
//计算累加频数,用户计数排序
for(int j=1;j<k;j++)
counts[j] = counts[j] + counts[j-1];
//使用倒数第i+1位数对A进行排序
for(int j=h;j>=l;j--){
index = (int)(A[j]/pval)%k;
temp[counts[index]-1] = A[j];
counts[index]--;
}
//将按第i为数排序后的结果保存回数组A中
for(int j=0;j<size;j++)
A[j+l] = temp[j];
//更新pval
pval = pval*k;
}
delete[] counts;
delete[] temp;
}
int main(){
int A[] = {712,303,4,18,89,999,70,26};
rxsort(A,0,7,3,10);
for(int i=0;i<8;i++)
cout<<A[i]<<" ";
}
如果上面那个网站进不去,可以去LeetCode或者牛客嘛