最近为了准备实习生面试,看了算法导论前面一部分的内容,还实现了一些常见的排序算法
现在稍微整理一下最近的工作,可能有些不足之处,实现的也是最简单的整形的操作,以后继续完善之。
首先是插入排序,插入排序的原理和我们打扑克一样,当你拿到一张新牌的时候,你会从后往前找,因为已经到手的部分是已经排序好的(如果你是高手乱序打牌请飘过)找到新牌可以插入的合适位置放入,然后继续拿牌。
代码如下
void insertSort(int* a,int len)//插入排序
{
int i=0,j=0;
int tmp;
for(i=1;i<len;i++)//数组第二个数字开始
{
j=i;
tmp = a[i];//记录插入的数字
while(j > 0 && tmp < a[j-1])//向前寻找位置插入
{
a[j]=a[j-1];
j--;
}
a[j]=tmp;
}
}
接着是冒泡排序,方法就是每次从头到上次结束的位置(初始为尾部)一一比较将最大的数字往最边上推,就像气泡往上升的过程,所以叫冒泡排序。代码如下
void swap(int& a,int& b)
{
int tmp;
tmp=b;
b=a;
a=tmp;
}
void bubbleSort(int* a,int len)
{
int i,j;
for(i = len-1; i>0 ; --i)
{
for( j= 0; j < i ; ++j)
{
if( a[j] > a[j+1] )
{
swap(a[j],a[j+1]);
}
}
}
}
二路归并排序,是一个很重要的排序,出现在外排序中,所以需要掌握,也是分治思想的一个好例子,直接上代码。
void merge(int *a,int left,int mid ,int right)//归并排序-合并
{
int i,j,k;
int n,m;
n= mid - left + 1;
m= right - mid;
int leftA[n+2];// 最好从堆里分配空间,数据量大了这个程序直接挂,限额是1M的栈容量
int rightA[m+2];
for(i=1;i<=n;i++)
{
leftA[i]=a[left+i-1];
}
for(i=1;i<=m;i++)
{
rightA[i]=a[mid+i];
}
leftA[n+1]=MaxInt;
rightA[m+1]=MaxInt;
i=1;
j=1;
for(k=left;k<=right;++k)
{
if( leftA[i] < rightA[j] )
{
a[k]=leftA[i++];
}
else
{
a[k]=rightA[j++];
}
}
}
void merge_sort(int *a,int left,int right)//归并排序主函数
{
if( left < right )
{
int mid=(left+right)/2;
merge_sort(a,left,mid);
merge_sort(a,mid+1,right);
merge(a,left,mid,right);
}
}
现在开始效率高点的排序了,快速排序和堆排序都是算法导论里所说的,理论上接近了比较排序法可以达到的最优复杂度O(NlogN)。如果想要再提升速度就只有另辟蹊径了,即采用非比较的排序,后面会说。
快速排序是典型的二分思想的应用,每次选取一个比较值,然后从前后同时开始向中间偏离,将左边大于比较值的和右边小于比较值的数字对换,直到左边的和右边的相遇。结束一轮,这样的结果是相遇的点上满足 左边的所有值都小于右边,然后递归调用该算法。
好像说的有些乱。。。看代码吧。
int qsort_partion(int* a,int start,int end)
{
int i=start,j=end;
int judge = a[ end ];//选择最后一个数字作为比较值
while(1)
{
while( a[i] < judge ) ++i;
--j;
while( a[j] > judge ) --j;
if( i >= j ) break;
else
{
swap(a[i],a[j]);//交换需要调整的值
++i;
}
}
swap(a[end],a[i]);//将当前值于比较值对换,然后就完成以i 为界,一边的值都小于a[i],另一边都大于a[i]
return i;
}
void quickSort(int* a, int start ,int end)
{
if(start <end )
{
int q = qsort_partion(a,start,end);
quickSort(a,start,q-1);
quickSort(a,q+1,end);
}
}
快排只要保证每次分割的调用是常数比例,即使是很不对称的 1/8 7/8 也可以满足O(NlogN)的复杂度,最怕有序的数组,简直是噩梦。因为每次选取最后值比较,其实每次都只遍历而无作为,会导致复杂度变成N的平方。所以真正能用的快排都会采用随机定位,和三数均值的方法防止这类问题。STL源码里引进了一种新的排序方法基于快排的,叫introSort 他其实就是加入了恶化处理机制(设置一个阀值,但递归次数超过这个值时候进行处理),对于有序数组,早些发现然后采用插入排序完成,插入排序对有序数组效率很高。
接下来是堆排序,堆排序有分最大堆和最小堆,实现机制反正差不多,我实现的是最大堆。
堆排序需要做的就是构建堆,堆调整(向上调整,和向下调整)然后就是排序的具体步骤了,这个理解起来确实不难,但我当时写加调试用了1个半小时。。基本功的问题。
上代码
void adjust_heap(int* a , int i)//调节该点 OK
{
int tmp = a[i];
while( i > 1 )
{
if( a[i>>1] < tmp )
{
a[i]=a[i>>1];
i>>=1;
}
else
{
break;
}
}
a[i] = tmp ;
}
void adjustDown_heap(int* a ,int size)
{
int tmp = a[1];
int i=1;
while( i<= size )//有孩子
{
if( 2*i > size ) break;//越界判断!!!!!
if( (2*i+1) > size)//只有一个孩子
{
if( tmp > a[2*i] )
{
break;
}
else
{
a[i]=a[2*i];
i=2*i;
continue;
}
}
if( tmp > a[2*i] && tmp > a[(2*i+1)])//两个孩子
{
break;
}
else//选择和较大的孩子节点替换
{
// cout<<"左孩子"<<2*i<<" 右孩子"<<2*i+1<<endl;
if( a[2*i] > a[(2*i+1)] )
{
a[i]=a[2*i] ;
i*=2;
}
else
{
a[i]=a[(2*i+1)];
i=2*i+1;
}
}
}
a[i] = tmp;
}
void make_heap(int* heap , int size )// OK
{
int i;
for(i=1;i<=size;i++)
{
adjust_heap(heap, i);
}
}
void heap_sort(int* src, int size)
{
int i;
int tmp;
make_heap(src, size);
for( i= 1 ; i <= size ; ++i )
{
tmp=src[size+1-i];//保存最后一个元素
src[size+1-i] = src[1];//将堆顶用最后个元素替代
src[1] = tmp;//最后一个元素替代堆顶
adjustDown_heap( src,size-i );//堆变小,进行调整
}
}
堆排序和快速排序都是原地排序,可以说这两个思想都太牛了,一般人很难想到的,我们站在巨人的肩膀上应该更加努力。。废话说多了,这两个都是渐进最优的比较排序算法。
那么还有更快的么,算法导论里给了几个,计数排序,基数排序,桶排序。
我仅仅实现了计数排序,但对三种排序都稍微做了了解。
计数排序就是用空间换时间,并不进行任何比较,就是对数字进行统计。然后根据统计结果直接放入新数组的指定位置,所以这个排序可以在O(N)的复杂度完成排序,但空间复杂度为O(N+M)N为数组长度,M为数值范围。需要指定一个数值的范围,开辟一个数组记录该数字出现的次数。上代码
const int range=1000;
void count_sort(int* a,int* b,int size)//计数排序,需要知道数据的范围range
{
int i;
int count[ range+1 ];
for( i=0;i<=range;++i )
{
count[i]=0;
}
for( i= 1 ;i <=size;++i )
{
count[a[i]]+=1;
}
for( i=1; i<=range;++i )
{
count[i]+=count[i-1];
}
for( i=1 ;i<=size;++i )
{
b[count[a[i]]]=a[i];
count[a[i]]-=1;
}
}
其实很容易看出来,range就是这种排序的限制,Short类型都有2的16次方大。。这个数组得开多大啊。。所以这样看,计数排序的意义就是为基数排序服务。基数排序就是把要排的数字分割成1个一个的位数,比如138 就是1, 3, 8
241 2, 4, 1
163 1, 6, 3
就拿上面的数字为例,先对个位排序得到
2,4,1
1,6,3
1,3,8
然后对十位进行排序得到
1,3,8
2,4,1
1,6,3
然后对百位进行排序
1,3,8
1,6,3
2,4,1
这样结果就出来了,所有的数字就可以分解成range=10的从最低位到最高位的计数排序。
这样假设有d 位,那么完成的复杂度就是O(d*N) 比快排快吧。。
至于桶排序的思想其实类似,就是将数值按照一定范围进行划分,将某个范围内的数值放到一起(这里称为桶),然后对放在一起的进行排序,再从每一个桶中读出已经排序好的元素。
这些代码都是以升序为目的的,没有使用任何高级C++技术。 排序就到这里了,欢迎点评指正!
分享到:
相关推荐
主要包括冒泡排序(两种思路实现)、冒泡排序的改进算法、选择排序法、插入排序法(两种实现方式)、快速排序法、归并排序法 (递归实现和非递归实现),该资料为本人亲自整理,且代码完整、注释全面!
在编程领域,C++是一种广泛使用的面向对象的编程语言,其强大的性能和灵活性使得它在处理数据和算法实现上有着广泛的应用。...在C++编程中,了解各种排序算法的适用场景和优缺点,是优化程序性能、提高代码质量的关键。
冒泡排序的核心思想是通过不断地交换相邻两个元素的位置来实现排序。具体步骤如下: 1. **第一轮**:从数组的第一个元素开始,依次比较相邻的两个元素。若前一个元素大于后一个元素,则交换它们的位置;若前一个元素...
由于其语法简洁,逻辑清晰,因此非常适合用来学习和实现各种算法,包括排序算法。 在MATLAB中,我们可以直接操作矩阵或数组,这使得冒泡排序的实现更为直观。基本的冒泡排序步骤如下: 1. **初始化**:首先,创建...
在计算机科学中,排序是处理数据的一种常见操作,用于将一组元素按照特定顺序排列。...这些排序算法的实现展示了不同的思路和技巧,理解它们的原理和性能特性对于优化算法和解决实际问题具有重要意义。
通过动手实践,不仅能够加深对各种排序算法工作原理的理解,还能够培养实际编程能力和算法优化思维。实验的具体目标包括: - **排序的基本概念**:理解排序算法的基本概念,特别是排序的稳定性和时间复杂度的重要性...
标题中的“MPI奇偶排序源代码+可运行程序”指的是一个使用MPI(Message Passing Interface)实现的并行算法,用于进行奇偶排序。这个程序基于MPICH2版本的MPI库,该库是MPI标准的一个开源实现,适用于分布式内存的多...
- 算法思路简单,易于实现。 - 对于小规模数据,效率较高。 3. **缺点** - 不稳定排序,相同元素可能会改变原有顺序。 - 效率较低,时间复杂度为O(n^2),不适用于大数据量排序。 4. **适用场景** - 适合于小...
这个压缩包包含的资源是优化过的VB实现的七种经典排序算法,这些算法不仅可以帮助理解排序的基本原理,还能通过记录时间和循环次数来分析不同算法的效率。以下是这7种经典排序算法的详细介绍: 1. 冒泡排序(Bubble...
除了冒泡排序,代码还展示了其他两种经典的排序算法:选择排序和插入排序。 选择排序的工作原理是每一次从待排序的数据元素中选出最小(或最大)的一个元素,存放在序列的起始位置,直到全部待排序的数据元素排完。...
在代码实现上,C++提供了丰富的工具和库函数,如STL中的`std::sort`,它一般使用了高效的排序算法(如introsort,结合了快速排序、堆排序和插入排序),适用于大多数情况。然而,了解并手动实现这些基本排序算法有助...
C语言代码实现下面是一份C语言实现归并排序算法的代码,代码内部有详细的注释,可以帮助理解代码:#include <stdio.h>void merge(int arr[], int l, int m, int r) { int i, j, k; int n1 = m - l + 1; int n2 = r -...
这是冒泡排序的核心实现,通过对链表进行多次遍历并调整节点的连接关系来实现排序。 这段代码实现了基于链表的冒泡排序过程,相比于传统的数组实现,链表版本的冒泡排序更加复杂,因为它涉及到指针的操作。尽管...
尽管第二种算法的具体实现代码可能有所不同,但基本思路保持一致。可能的变化在于循环结构的实现方式或者条件判断的细节,不过最终目的仍然是实现从小到大的排序。这种变化可能是为了优化代码的效率或者提高可读性,...
在IT领域,排序算法是计算机科学中的基础但至关重要的概念,尤其对于编程面试来说,对各种排序算法的理解和实现能力是衡量候选人技能的重要标准。在这个“排序面试题代码”压缩包中,包含了直接插入排序和希尔排序两...
`堆排序思路.txt`和`基数排序算法.txt`文件提供了这些排序算法的详细解释和思路,帮助理解它们的工作原理。在实际编程中,根据数据的特点和性能需求,选择合适的排序算法至关重要,例如基数排序对于大量整数排序尤其...
1. 直接插入排序:通过不断将未排序元素插入已排序序列的正确位置,实现排序。时间复杂度在最坏情况下为O(n^2)。 2. 冒泡排序:通过相邻元素两两比较并交换,使最大(或最小)元素逐渐“冒”到序列末尾。时间复杂度...
本文将深入探讨如何使用多线程来实现冒泡排序和快速排序这两种经典的排序算法,这对于初学者来说是一次很好的学习机会。 首先,让我们理解冒泡排序。冒泡排序是一种简单直观的排序算法,它的基本思想是通过重复遍历...
主要代码实现 选择排序 简介 复杂度与稳定性 过程介绍(以顺序为例) 图示过程: 代码实现 插入排序 简介 复杂度与稳定性 过程介绍 图示过程 代码实现 希尔排序 简介 复杂度与稳定性 过程介绍 图示...
本文将详细介绍这两种排序算法,并结合C语言的实现,深入解析其工作原理和代码实现。 **合并排序(Merge Sort)** 合并排序是一种分治算法,由美国计算机科学家John von Neumann于1945年提出。其主要思路是将大...