一、选择排序
思路:将总的array分成两个部分,一部分是已经排好序的subarray1,另一部分是待排序的subarray2,每次都从subarray2中选择最小的加入到subarray1中,直至所有的元素加入到subarray1中。
实现:
Void swap(int *xp,int *yp)
{
Int t=*xp;
*xp=*yp;
*yp=t;
}
Void selecttionSort(int arr[],int n)
{
Int i,j,minIndex;
For(i=0;i<n-1;i++)
{
minIndex=i;
For(j=i+1;j<n;j++)
{
If(arr[j]<arr[minIndex])
{
minIndex=j;
}
}
Swap(&arr[i],arr[minIndex]);
}
}
时间复杂度:O(n*n)
二、冒泡排序
思路:将总的array分成两个部分,一部分是已经排好序的subarray2,另一部分是待排序的subarray1,每次都比较临近的两个元素,将较小的的元素置于较大元素之前。遍历一轮之后可找到最大的元素以交换置subarray1末尾,将subarray1中的最后元素归入subarray2中
实现:
Void swap(int *xp,int *yp)
{
Int t=*xp;
*xp=*yp;
*yp=t;
}
void bubbleSort(int arr[],int n)
{
int i,j;
for(i=0;i<n-1;i++)
{
for(j=1;j<n-i;j++)
{
if(arr[j]<arr[j-1])
{
swap(&arr[j],&arr[j-1]);
}
}
}
}
时间复杂度:O(n*n)
但是上面的算法存在一些缺陷,就是当input的是一个有序的array时,依然需要O(n*n)的时间,我们可以改进使得当input的是一个有序array时,时间复杂度为O(n).
改进之后:
void bubbleSort(int arr[],int n)
{
int i,j;
bool swapped; /*增加一个判断是否进行交换的变量,如果遍历一遍依然没有进行交换,说明array是有序的*/
for(i=0;i<n-1;i++)
{
swapped=false;
for(j=1;j<n-i;j++)
{
if(arr[j]<arr[j-1])
{
swap(&arr[j],&arr[j-1]);
swapped=true;
}
}
if(swapped==false)
{
break;
}
}
}
三、插入排序
思路:将总的array分成两个部分,一部分是已经排好序的subarray1,另一部分是待排序的subarray2。每次都取出subarray2中的第一个元素,将其插入到subarray1中正确的位置,使得subarray1有序。
实现:
void insertionSort(int arr[],int n)
{
int i,j,key;
for(i=1;i<n;i++)
{
key=arr[i];
j=i-1;
while(j>=0&&arr[j]>key)
{
arr[j+1]=arr[j];
j--;
}
arr[j+1]=key;
}
}
时间复杂度:O(n*n)
四、归并排序
思路:运用分而治之的思想,将大规模的array分解成许多小规模的subarray,将小规模的subarray排成有序之后再组装成有序的array。
实现:
void merge(int arr[],int l,int m,int r)
{
int i,j,k;
int n1=m-l+1;
int n2=r-m;
int L[n1+1],R[n2+1];
for(int i=0;i<n1;i++)
{
L[i]=arr[l+i];
}
for(j=0;j<n2;j++)
{
R[j]=arr[m+1+j];
}
L[i]=INT_MAX;
R[j]=INT_MAX;
i=0;
j=0;
for(k=l;k<=r;k++)
{
if(L[i]<R[j])
{
arr[k]=L[i];
i++;
}else
{
arr[k]=R[j];
j++;
}
}
}
void mergeSort(int arr[],int l,int r)
{
if(l<r)
{
int m=(l+r)/2;
mergeSort(arr,l,m);
mergeSort(arr,m+1,r);
merge(arr,l,m,r);
}
}
时间复杂度:O(nLogn)
五、堆排序
思路: 1.建堆,升序为大顶堆,降序为小顶堆
2.交换堆顶元素与最后一个元素
3.堆的规模减1
4.维持大顶堆的性质
5.重复2,3,4直到堆的规模为1
实现:
void heapify(int arr[],int n,int i)
{
int largest=i;
int l=2*i+1;
int r=2*i+2;
if(l<n&&arr[l]>arr[largest])
{
largest=l;
}
if(r<n&&arr[r]>arr[largest])
{
largest=r;
}
if(largest!=i)
{
swap(&arr[largest],&arr[i]);
heapify(arr,n,largest);
}
}
void heapSort(int arr[],int n)
{
int i;
//建堆
for(i=n/2-1;i>=0;i--)
{
heapify(arr,n,i);
}
//交换
for(i=n-1;i>0;i--)
{
swap(&arr[0],&arr[i]);
heapify(arr,i,0);//维持堆的性质
}
}
时间复杂度:O(nLogn)
六、快速排序
思路:
与mergeSort一样,都运用了分而治之的思想。不同的是quickSort将array分成三部分:中间元素pivot,比pivot都小的subarray1,和比pivot都大的subarray2.
实现:
int partition(int arr[],int l,int r)
{
int pivot=arr[r];
int i=l-1;
int j;
for(j=l;j<r;j++)
{
if(arr[j]<pivot)
{
i++;
swap(&arr[j],&arr[i]);
}
}
swap(&arr[i+1],&arr[r]);
return i+1;
}
void quickSort(int arr[],int l,int r)
{
if(l<r)
{
int pi=partition(arr,l,r);
quickSort(arr,l,pi-1);
quickSort(arr,pi+1,r);
}
}
时间复杂度:
Average Case : O(nLogn)
Worst Case : O(n*n)
而为了最大程度的避开Worst Case,我们可以采用随机版本的quickSort
int randomNum(int l,int r)
{
srand((unsigned int)time(NULL));
return rand()%(r-l+1)+l;
}
int randomizedPartition(int arr[],int l,int r)
{
int ran=randomNum(l,r);
swap(&arr[ran],&arr[r]);
return partition(arr,l,r);
}
void randomizedQuickSort(int arr[],int l,int r)
{
if(l<r)
{
int pi=randomizedPartition(arr,l,r);
randomizedQuickSort(arr,l,pi-1);
randomizedQuickSort(arr,pi+1,r);
}
}
<!--EndFragment-->
相关推荐
35种基于比较的内部排序算法的动态图示分析和演示
基于FPGA的并行全比较排序算法.pdf
java写的基于比较的各种排序算法,都是一个一个的小函数。简单排序包括:选择排序,插入排序,折半插入排序,冒泡排序。 分治思想的排序包括:归并排序,快速排序,堆排序。 程序把随机生成的整数进行排序,开始时用...
排序算法是一种基本并且常用的算法。由于实际工作中处理的数量巨大,所以排序算法 对算法本身的速度要求很高。 而一般我们所谓的算法的性能主要是指算法的复杂度,一般用O方法来表示。在后面我将 给出详细的说明...
基于教材内容,任选两种排序算法,实现并比较性能。 基本要求 (1)至少要有一种排序算法的性能优于 O(n2 ) (2)对实现的排序算法进行实验比较,实验比较数据参见教材 7.8 章节 (3)排序算法要基于教材,测试输入...
基于姓名排序算法动态演示系统的设计与实现,使用java开发语言
基于mfc的内排序算法动态演示,可实现多个算法同时演示对比,界面有皮肤,可实现界面缩放。
浅析基于C语言的常用排序算法比较.pdf
排序学习技术尝试用机器学习的...对近些年基于排序学习的推荐算法研究进展进行综述,并对其问题定义、关键技术、效用评价、应用进展等进行概括、比较和分析.最后,对基于排序学习的推荐算法的未来发展趋势进行探讨和展望.
基于javascript的排序算法源码,包括冒泡排序、选择排序、希尔排序、插入排序、快速排序、归并排序、基数排序、堆排序
基于邻接表存储的图的拓扑排序算法,学习C++和理解数据结构很有帮助
本项目用C++中实现了冒泡排序、插入排序、堆排序、希尔排序、归并排序、基数排序、选择排序、桶排序、快速排序
文档中包含了排序算法的五种常用的方法,包括思想,算法实现,及运行结果,不错的话记得点评评论一下啊。
上述各种排序方法都是基于比较的内排序,其时间主要消耗在排序过程中进行的记录的比较和移动,因此,统计在相同数据状态下不同排序算法的比较次数和移动次数,即可实现比较各种排序算法的目的。 [思考题]如果测算每...
数据结构中基于分治策略的排序算法探讨数据结构中基于分治策略的排序算法探讨
排序算法 排序算法_基于C语言实现的排序算法之QuickSort实现
排序算法 排序算法_基于C语言实现的排序算法之BubbleSort实现
排序算法 排序算法_基于C语言实现的排序算法之CycleSort实现
排序算法 排序算法_基于C语言实现的排序算法之MergeSort实现
排序算法 排序算法_基于C语言实现的排序算法之PancakeSort实现