算法基础 排序(一)
桶排序
冒泡排序
快速排序
1.桶排序
所谓的桶排序就是列出所有的可能进行排序
//9,4,2,7,5,2,9,10,1 用来排序的数组 并且确定这些数字的可能为0到10的整数
int arr[] = {9,4,2,7,5,2,9,10,1};
//声明11个桶,对应所有的可能
int bucketArr[11] = {0};
//用来打印的数组
NSMutableString *reslutStr = [NSMutableString string];
//确定用来排序的数组的个数
int count = sizeof(arr)/4;
//遍历要排序的数组,比如遍历到一个数是5,那么就在5(bucketArr[5])对应的那个桶加1
int i;
for (i = 0; i < count; i++) {
bucketArr[arr[i]]++;
}
//遍历所有的桶,如果第6个桶(bucketArr[5])对应的数字是2,那就输出两个5
int j;
for (i = 0; i < 11; i++) {
for (j = 0; j < bucketArr[i]; j++) {
//结果加到可变字符串中
[reslutStr appendFormat:@"%d ",i];
}
}
//打印结果
NSLog(@"%@",reslutStr);
桶排序结果.png
(可以忽略第一句话,只是说明程序可以换种输入方式)
上面的程序中,你可以放一个输入函数,直接确定输入n个数,然后每次输入直接加到对应的桶里面.
但是我们依然要执行n次的将数放入桶中,
再执行m次的遍历桶和n次的把数字加到可变数组中.m为桶的个数.
所以时间复杂度就是m+2n.我们在计算时间复杂度时会忽略较小的常数.所以最终的时间复杂度就是O(M+N)
小结:这里的桶排序只是简化版的.桶排序是所有排序中最快的,当然是大多数情况下.当然也有一些缺点,比如他很费内存.因为他要列出所有的可能.比如可能性必须是有限的,出现小数他就没辙了.
2.冒泡排序
冒泡排序就是比较相邻两个数进行排序
//9,4,2,7,5,2,9,10,1,53,32,24 从大到小排序
int arr[] = {9,4,2,7,5,2,9,10,1,53,32,24};
//得到数组元素个数
int count = sizeof(arr)/4;
int i,j,sub;
for (j = 0; j < count - 1; j++) {//比如{3,5,2,6} 如果你要把6移到第一个位置,你需要重复排序3遍 所以这里重复count-1次
for (i = 0; i < count - 1; i++) {//重头到尾排一遍
if (arr[i] < arr[i+1]) {
//交换位置
sub = arr[i];
arr[i] = arr[i+1];
arr[i+1] = sub;
}
}
}
//数组遍历打印
for (i = 0; i < count; i++) {
printf("%d ",arr[i]);
}
冒泡排序结果.png
这里如果我们有n个数需要进行排序,那么我们一次排序需要进行n-1遍,然后需要重复排序n-1次才能保证完全排序.一共需要(n-1)²
所以这里我们的时间复杂度就是O(N²)
小结:冒泡排序除了逻辑简单以外,就没什么优点了.他的时间复杂度让人很失望.
3.快速排序
快速排序用的是分治合并的思想(不知道有没有这种思想,我觉得这么说挺通的,😈😈😈)
int arr[] = {9,4,2,7,5,2,9,10,1,53,32,24};
int count = sizeof(arr)/4;
//找一个基准数 为了方便就把第一个数当做基准数 然后将比基数小的放基数左边,比基数大的放基数右边
int i = 1;
int j = count - 1;
int base = arr[0];
int sub ;
while(i!=j)
{
//让j先进行探测,能确保最后一次交换是将基数与比基数小的值交换
while(arr[j]>=base && i<j)
j--;
//再从左往右找
while(arr[i]<=base && i<j)
i++;
//交换两个数在数组中的位置
if(i<j)//当i!=j
{
sub=arr[i];
arr[i]=arr[j];
arr[j]=sub;
}
}
//相等交换基数
arr[0]=arr[i];
arr[i]=base;
这里是快速排序的一次排序,一次排序过后我们等到两个数组,基数左边和右边,然后我们需要对其进行再排序,于是就想到用递归.毕竟你不好用循环做.
当只有一个数的时候跳出递归
整理后得到
//9,4,2,7,5,2,9,10,1,53,32,24 从小到大排序
int arr[] = {9,4,2,7,5,2,9,10,1,53,32,24};
void quickSort(int left,int right){
if (left >= right) {
return;
}
int base = arr[left];
int i = left;
int j = right;
int sub;
while(i!=j)
{
//让j先进行探测,能确保最后一次交换是将基数与比基数小的值交换
while(arr[j]>=base && i<j)
j--;
//再从左往右找
while(arr[i]<=base && i<j)
i++;
//交换两个数在数组中的位置
if(i<j)//当i!=j
{
sub=arr[i];
arr[i]=arr[j];
arr[j]=sub;
}
}
//相等交换基数
arr[left]=arr[i];
arr[i]=base;
quickSort(left, i-1);
quickSort(i+1, right);
}
int main(int argc, const char * argv[]) {
@autoreleasepool {
int count = sizeof(arr)/4;
quickSort(0, count-1);
for (int i = 0; i < count; i++) {
printf("%d ",arr[i]);
}
}
快速排序结果.png
接下来就谈谈他的时间复杂度
http://www.cnblogs.com/pugang/archive/2012/07/02/2573075.html
这篇博客里对其进行了一定的说明,他是用一个公式来说明的.
然后我想说的是,我换种方式,自己计算了一下他的时间复杂度,要是错了(反正我觉得不会有多少人来看),你说我就改.
首先第一次排序,最好的是分成平均分成两部分 那么第一次排序进行了n/2次 确定了1个数字的位子.
第二次排序 也是进行了n/2次 这里的是算上两部分一共的次数,确立的两个数字
第三次...
然后得到
第1次 运行n/2 确立2^0个数字
第2次 运行n/2 确立2^1个数字
第3次 运行n/2 确立2^2个数字
...
第x次 运行n/2 确立2^(x-1)个数字
此时满足 2^0 + 2^1 +2^2 + 2^ 3 +...+2^(x-1) = n;
解得 x = log(n+1) 这里2为默认底.
然后时间复杂度就是 x * n/2 = n/2 log(n+1)
计算时间复杂度时忽略较小的数字 所以就得到O(nlogn).
而最坏的结果是每一次选中的基数都是最大或者最小的数,然后相当于每次运行n-1 ,n-2,n-3,n-4,n-5..所以我们可以认为程序一共执行了(n^2 - n)/2 次 所以时间复杂度就是O(N^2).
