怎样在网站图片上做店铺广告,网站建设维护多少钱,做网站页面该建多大的画布,北京营销网站建设公司排序算法是面试中常见的问题#xff0c;不同算法的时间复杂度、稳定性和适用场景各不相同。按照数据量和存储方式可以将排序算法分为 内排序#xff08;Internal Sorting#xff09;和 外排序#xff08;External Sorting#xff09;。
内排序是指对所有待排序的数据都可…排序算法是面试中常见的问题不同算法的时间复杂度、稳定性和适用场景各不相同。按照数据量和存储方式可以将排序算法分为 内排序Internal Sorting和 外排序External Sorting。
内排序是指对所有待排序的数据都可以一次性加载到内存中进行排序。这意味着所有的数据都可以直接在计算机的内存中操作无需借助外部存储设备如硬盘。内排序算法的设计可以更加灵活因为内存操作速度远远高于磁盘操作速度。常见的内排序算法包括快速排序、归并排序、插入排序、冒泡排序等。
外排序是指对大量数据进行排序时由于数据无法一次性加载到内存中需要借助外部存储设备进行排序。通常在外排序中数据会被分成若干个小块每次只处理其中一部分数据然后将部分排序好的数据存储回外部存储设备再进行合并等操作。外排序算法需要考虑数据的分块、读写外部存储的效率以及合并有序数据等问题。常见的外排序算法有多路归并排序、置换选择排序等。
本文介绍的都是常见的内排序算法插入排序、冒泡排序、选择排序、希尔排序、归并排序、快速排序、堆排序、桶排序。 目录 1. 插入排序2. 冒泡排序3. 选择排序4. 希尔排序5. 归并排序6. 快速排序7. 堆排序8. 桶排序 1. 插入排序
插入排序的核心是将待排序的元素逐个插入到已经排好序的序列中以构建有序的输出序列
void inssort(int A[],int n){for(int i1;in;i){for(int ji;j0;j--){if(A[j]A[j-1]){ //A[j]A[j-1](此处小于即排在前面)swap(A,j,j-1);}else{break; //A[j]已达到正确位置(时间优化)}}}
}插入排序的平均时间复杂度为 O(n2)最好情况为 O(n)最坏情况为 O(n2)适用于小规模的数据集或者已经基本有序的数据。插入排序的空间复杂度为 O(1)是一种稳定排序算法。
2. 冒泡排序
冒泡排序的核心思想是通过比较相邻的元素并交换位置逐渐将最小的元素 “冒泡” 到正确的位置。冒泡排序的过程类似于冒泡泡沫在水中升起的过程较大的元素会逐渐向序列的开头 “冒泡”
void bubsort(int A[],int n){for(int i0;in-1;i){for(int jn-1;ji;j--){if(A[j]A[j-1]){swap(A,j,j-1);}}}
}冒泡排序的平均时间复杂度为 O(n2)最好情况和最坏情况都为 O(n2)。冒泡排序的空间复杂度为 O(1)是一种稳定排序算法。
3. 选择排序
选择排序的核心思想是在未排序序列中选择最小的元素然后将它与未排序序列的起始位置交换使得已排序序列逐步增长
void selsort(int A[],int n){for(int i0;in-1;i){int indexi;for(int jn-1;ji;j--){if(A[j]A[index]){indexj;}}swap(A,i,index);}
}选择排序的平均时间复杂度为 O(n2)最好情况和最坏情况都为 O(n2)。选择排序的空间复杂度为 O(1)是一种稳定排序算法。
4. 希尔排序
希尔排序利用了插入排序最佳时间代价特性在不相邻的记录之间进行交换和比较。核心思想是将整个序列分成多个较小的子序列来逐步减少序列的无序度从而在最后一步进行一次插入排序达到提高排序速度的效果。过程如图
void inssort2(int A[],int n,int incr){ //n为传入数组长度incr为数组内元素间隔for(int iincr;in;iincr){ //incr相当于第1位元素incr相当于间隔for(int ji;(jincr)(A[j]A[j-incr]);j-incr){int tmpA[j];A[j]A[j-incr];A[j-incr]tmp;cnt1;}}
}
void shellsort(int A[],int n){for(int in/2;i2;i/2){ //i表示组数或者间隔for(int j0;ji;j){ //j表示有i组数据时从0到i遍历inssort2(A[j],n-j,i); //对第j组数据进行插入排序起始位置长度间隔//第j组数据在A中下标:j,ji,j2i...用inssort2中传入参数表示为:A[j],A[j]i,A[j]2i...}}inssort2(A,n,1); //对整个数组插入排序
}希尔排序在现实中没有对应的直观解释也无法证明其时间复杂度一般认为平均时间复杂度为 O(n1.5)最好情况为 O(nlogn)最坏情况为 O(n2)。希尔排序的空间复杂度为 O(1)是一种不稳定排序算法。
5. 归并排序
归并排序的核心思想是 “二分合并”即将一个未排序的数组分割成两个子数组递归地对这两个子数组排好序后再合并为一整个有序的数组
void mergesort(int A[],int tmp[],int left,int right){ //left表示A[0]下标right表示A[n-1]下标if(leftright) return;int mid(leftright)/2;mergesort(A,tmp,left,mid); //向下递归二分集合并排序mergesort(A,tmp,mid1,right);for(int ileft;iright;i){tmp[i]A[i];}int i1left,i2mid1; //i1,i2表示两个待合并数组各自都已排序首个未排序元素下标for(int currleft;currright;curr){if(currmid1){ //left数组已完成合并A[curr]tmp[i2];}else if(i2right){ //right数组已完成合并A[curr]tmp[i1];}else if(tmp[i1]tmp[i2]){A[curr]tmp[i1];}else{A[curr]tmp[i2];}}
}归并排序的平均时间复杂度为 O(nlogn)最好情况和最坏情况也都为 O(nlogn)。归并排序的空间复杂度为 O(n)是一种稳定排序算法。
6. 快速排序
快速排序的核心思想是选择一个轴值 pivot将数组分为小于轴值的部分和大于轴值的部分然后递归地对这两部分进行排序。轴值的选择会影响算法的效率一般选取数组的中间点作为轴值。为了设计方便会将轴值置于数组末端待排好序后再移动到合适位置
//partition函数将数组的l1~r-1划分为两个以轴值为分界的部分并返回轴值的下标实际上该位元素与最后一位交换后才是真正的轴值下标
int partition(int A[],int l,int r,int pivot){ //l,r为A[]的左右范围pivot为轴值do{while(A[l]pivot); //跳过满足小于轴值的元素终止在大于轴值的地方while((lr)(A[--r]pivot));int tmpA[r];A[r]A[l];A[l]tmp;}while(lr);return l;
}void qsort(int A[],int i,int j){if(ij) return;int pivotindex(ij)/2; //选取轴值int pivotA[pivotindex];A[pivotindex]A[j]; //将轴值与末尾元素互换A[j]pivot;pivotindexpartition(A,i-1,j,A[j]); //将l1~r-1按轴值分部并返回待与轴值交换元素下标pivotA[j]; //轴值还在末尾等待交换A[j]A[pivotindex];A[pivotindex]pivot;qsort(A,i,pivotindex-1);qsort(A,pivotindex1,j);
}快速排序是迄今为止所有内排序算法中在平均情况下最快的一种当每个轴值都把数组分成相等的两个部分时整个算法的时间代价是 Θ \Theta Θ(nlogn)。快速排序的平均时间复杂度为 O(nlogn)最好情况为 O(nlogn)最坏情况为 O(n2)。快速排序的空间复杂度为 O(logn)是一种不稳定排序算法。
7. 堆排序
堆排序是基于堆数据结构的排序算法它利用最小堆的性质来实现对数组的排序
class heap{
private:int* Heap;int maxsize;int n;void siftdown(int pos){while(!isLeaf(pos)){int jleftchild(pos); //下面j表示的是lc和rc中较小值的下标int rcrightchild(pos);if((rcn)(Heap[rc]Heap[j])){jrc;}if(Heap[pos]Heap[j]){return;}int tmpHeap[pos];Heap[pos]Heap[j];Heap[j]tmp;posj;}}
public:heap(int* h,int num,int max){Heaph;nnum;maxsizemax;buildHeap();}int size(){return n;}bool isLeaf(int pos){return (posn/2)(posn);}int leftchild(int pos){return 2*pos1;}int rightchild(int pos){return 2*pos2;}int parent(int pos){return (pos-1)/2;}void buildHeap(){for(int in/2-1;i0;i--){siftdown(i);}}void insert(const int it){int currn;Heap[curr]it;while((curr!0)(Heap[curr]Heap[parent(curr)])){int tmpHeap[curr];Heap[curr]Heap[parent(curr)];Heap[parent(curr)]tmp;currparent(curr);}}int removefirst(){n--;int tmpHeap[0];Heap[0]Heap[n];Heap[n]tmp;if(n!0){siftdown(0);}return Heap[n];}int remove(int pos){if(pos(n-1)){n--;}else{n--;int tmpHeap[pos];Heap[pos]Heap[n];Heap[n]tmp;while((pos!0)(Heap[pos]Heap[parent(pos)])){int tmpHeap[pos];Heap[pos]Heap[parent(pos)];Heap[parent(pos)]tmp;posparent(pos);}if(n!0){siftdown(pos);}}return Heap[n];}
};
void heapsort(int A[],int n){int minval;heap H(A,n,n);for(int i0;in;i){minvalH.removefirst();}
}堆排序的平均时间复杂度为 O(nlogn)最好情况和最坏情况也都为 O(nlogn)但比快速排序要慢一个常数因子。堆排序在实际使用时适用于查找第 k 大小的元素或者用于外排序。堆排序的空间复杂度为 O(1)是一种不稳定排序算法。
8. 桶排序
桶排序的核心思想是将数组按数值范围放入若干个桶每个桶对应一定范围的数据然后对每个桶中的数据使用其他排序算法或递归方式进行排序最后将所有桶中的数据按顺序合并得到排序结果
void inssort(int A[],int n){for(int i1;in;i){for(int ji;j0;j--){if(A[j]A[j-1]){int tmpA[j];A[j]A[j-1];A[j-1]tmp;}else{break;}}}
}void bucketSort(int A[],int n,int numBuckets){//创建桶int buckets[numBuckets][n]; //二维数组每行表示一个桶int bucketSizes[numBuckets]; //每个桶中元素的数量//初始化桶的大小for(int i0;inumBuckets;i){bucketSizes[i]0;}//确定数组元素范围int maxA-999,minA999;for(int i0;in;i){if(A[i]maxA) maxAA[i];if(A[i]minA) minAA[i];} //将元素放入桶中for(int i0;in;i){int bucketGapceil((maxA-minA)/(float)numBuckets);int bucketIndex(A[i]-minA)/bucketGap;buckets[bucketIndex][bucketSizes[bucketIndex]]A[i];}//对每个桶中的元素进行插入排序for(int i0;inumBuckets;i){inssort(buckets[i],bucketSizes[i]);}// 合并桶中的元素int index0;for(int i0;inumBuckets;i){for(int j0;jbucketSizes[i];j){A[index]buckets[i][j];}}
}桶排序的平均时间复杂度为 O(n2)最好情况和最坏情况也都为 O(n2)但比插入排序要快一个常数因子。桶排序适用于在已知输入数据的范围内进行排序若数据分布不均匀也会影响效率。桶排序的空间复杂度为 O(n2)是一种稳定排序算法。
