十大排序算法C++实现

稳定性

概念：序列中值相同的元素，排序后的相对位置继续不变

算法

最好时间

最坏时间

平均时间

额外空间

稳定性

冒泡排序

$ n $

$ n^2 $

$ n^2 $

1

稳定

选择排序

$ n^2 $

$ n^2 $

$ n^2 $

1

稳定

插入排序

$ n $

$ n^2 $

$ n^2 $

1

稳定

希尔排序

$ n $

$ n^2 $

$ n^{1.3}(nonexplict) $

1

不稳定

归并排序

$ nlogn $

$ nlogn $

$ nlogn $

n

稳定

快速排序

$ nlogn $

$ nlogn $

$ nlogn $

1

不稳定

堆排序

$ nlogn $

$ nlogn $

$ nlogn $

1

不稳定

基数排序

$ d*(n+k) $

$ d*(n+k ) $

$ d* (n+k) $

n+k

稳定

计数排序

$ n+m $

$ n + m $

$ n + m $

m

稳定

桶排序

n

n

n

n

稳定

注：

冒泡算法，一个优化是，在内层循环设置一个变量，用于标记循环是否进行了交换，当数组是排序完毕的，最好时间为n

希尔排序：希尔排序是简单插入排序的一个变种，目的是为了减少插入排序的不必要的数据移动。一个递减的step作为插入排序的滑动窗口大小，在滑动窗口内进行插入排序，最后step=1的步骤中，移动的数据相对较少。

归并排序的递归表达为：

\[T(n)=2T(\frac{n}{2})+f(n)

\]

所以时间复杂度为：O(nlogn)

归并排序的数组实现如下：

//归并排序

void mergeSortRecursive(vector &a, vector &b, int begin, int end){

if(begin>=end) return;

int m=begin+(end-begin)/2;

mergeSortRecursive(a, b, begin, m);

mergeSortRecursive(a, b, m+1, end);

int i=begin, j=m+1;

int idx=begin;

while(i<=m && j<=end){

b[idx++] = a[i]

}

while(i<=m) b[idx++]=a[i++];

while(j<=end) b[idx++]=a[j++];

for(int k=begin;k<=end;k++) a[k]=b[k];

}

void mergeSort(vector &v){

int n=v.size();

vector v_tmp(n);

mergeSortRecursive(v, v_tmp, 0, n-1);

}

归并排序的单链表实现如下：

//main.cpp

#include

#include

using namespace std;

struct ListNode{

int val;

ListNode *next;

ListNode(int x){

val=x;

next=NULL;

}

};

//归并排序

ListNode *mergeList(ListNode *heada, ListNode *headb){

ListNode *pre=new ListNode(-1);

ListNode *res=pre;

ListNode *p1=heada, *p2=headb;

while(p1&&p2){

if(p1->valval){

pre->next=p1;

p1=p1->next;

}else{

pre->next=p2;

p2=p2->next;

}

pre = pre->next;

}

if(p1) pre->next=p1;

if(p2) pre->next=p2;

return res->next;

}

ListNode *mergeSort(ListNode *head){

if(!head||head->next==NULL) return head;

ListNode *slow=head, *fast=head->next;

while(fast&&fast->next){

slow=slow->next;

fast=fast->next->next;

}

ListNode *heada=head, *headb=slow->next;

slow->next=NULL;

return mergeList(mergeSort(heada), mergeSort(headb));

}

int main(){

//1,8,3,7,3,8,10,18

ListNode *root = new ListNode(1);

root->next=new ListNode(8);

root->next->next=new ListNode(3);

root->next->next->next=new ListNode(7);

root->next->next->next->next=new ListNode(3);

root->next->next->next->next->next=new ListNode(8);

root->next->next->next->next->next->next=new ListNode(10);

root->next->next->next->next->next->next->next=new ListNode(18);

ListNode *newroot=mergeSort(root);

while(newroot){

cout<val<<" ";

newroot = newroot->next;

}

return 0;

}

快速排序

//快速排序

int partition(vector &v, int begin, int end){

int pivolt=v[begin];

int mark=begin;

for(int i=begin+1;i<=end;i++){

if(v[i]

mark++;

swap(v[mark], v[i]);

}

}

v[begin] = v[mark];

v[mark] = pivolt;

return mark;

}

void quickSortRecursive(vector &v, int begin, int end){

if(begin>=end) return;

int pivoltIdx=partition(v, begin, end);

quickSortRecursive(v, begin, pivoltIdx-1);

quickSortRecursive(v, pivoltIdx+1, end);

}

void quickSort(vector &v){

int n=v.size();

quickSortRecursive(v, 0, n-1);

}

基数排序，其中d为数组序中最大的位数，k为基数

计数排序，m为数组序的最大值

排序算法C++完整代码

参考链接