含有重复字符的字符串全排列算法虽然排序算法是⼀个简单的问题，但绝对是笔试⾯试的基础考点，重重之重。来个排序问题都没回答出来，留给⾯试官的印象也就那样了。
排序主要分为：
⽐较排序：快速排序、堆排序、归并排序、插⼊排序、希尔排序、选择排序、冒泡排序
⾮⽐较排序：基数排序、计数排序、桶排序
性能⽐较点：
时间复杂度：⼀般⽽⾔，好的性能是O(nlgn)，且坏的性能是O(n^2)。对于⼀个排序理想的性能是O(n)
稳定性：是否能让原本有相等键值的纪录维持相对次序。
⼀、插⼊排序
《算法导论》的第2章介绍了插⼊排序及其算法分析。
核⼼：有序序列+直接插⼊
描述：维持⼀个有序区，将⽆序区的第⼀个元素直接插⼊到有序区，形成新的有序序列，最终实现排序。最优、平均、最差时间复杂度为θ(n^2)。
算法步骤为：
1、从第⼀个元素开始，该元素可以认为已经被排序
2、取出下⼀个元素，在已经排序的元素序列中从后向前扫描
3、如果该元素（已排序）⼤于新元素，将该元素移到下⼀位置
4、重复步骤3，直到到已排序的元素⼩于或者等于新元素的位置
5、将新元素插⼊到该位置后
6、重复步骤2~5
上图：
伪代码为：
[cpp] view plain copy
INSERTION-SORT(A)
for j <- 2 to length[A]
do key <- A[j]
Insert A[j] into the sorted sequence A[1..j-1]
i  <- j-1
while i>0 and A[i]>key
do A[i+1] <- A[i]
i  <- i-1
A[i+1] <- key
实现：
[cpp] view plain copy
#include<assert.h>
#include<iostream>
#include<algorithm>
#include<iterator>
usingnamespace std;
voidinsert_sort(int *a,int len){
assert(a!=NULL && len>0);
int key=0,i=0;
for(int pos=1;pos<len;++pos){
key = a[pos];
i = pos-1;
while(i>=0 && a[i]>key){//backward
a[i+1]=a[i];
i--;
}
a[i+1] = key;
}
}
int main(){
int seq[]={3,7,8,5,2,1,9,5,4};
int length=sizeof(seq)/sizeof(int);
copy(seq,seq+length,ostream_iterator<int>(cout,""));
cout<<endl;
insert_sort(seq,length);
copy(seq,seq+length,ostream_iterator<int>(cout,""));
cout<<endl;
return0;
}
结果：
Eg. 请写出链表的插⼊排序程序 (copy过来的)
[cpp] view plain copysort of link什么意思
template<typenameT>
structlist_node{
struct list_node<T> *next;
T value;
};
template<typenameT>
struct _list{
struct list_node<T> *head;
int size;
};
template<typenameT>
voidSortLink(struct _list<T> * link) {
struct list_node<T>*pHead,*pRear,*p,*tp;
if (!link) return;
for(pHead=link->head,pRear=0;pHead;pHead=pHead->next) {
for(tp=pHead,p=pHead->next;p;tp=p,p=p->next)
if (pHead->value>=p->value)
tp->next=p->next,p->next=pHead,pHead=p,p=tp;
if (!pRear) link->head=pHead;
pRear=pHead;
}
}
⼆、⼆分查排序
⼆分查排序是插⼊排序的⼀个变种。改进点：对有序区从末尾⼀个⼀个直接⽐较，改为效率更⾼的⼆
分查。在速率上有⼀定的提升。⼆分插⼊排序元素移动次数与直接插⼊排序相同，最佳情况O(nlgn)，最差和平均情况O(n^2)实现：
[cpp] view plain copy
voidbinary_insert_sort(int *a,int len){
assert(a!=NULL && len>0);
int begin=0,end=0,middle=0;
int key=0,i=0;
for(int pos=1;pos<len;++pos){
key = a[pos];
begin=0;
end=pos-1;
while(begin<=end){
middle = (begin+end)/2;
if(a[middle]>key)
end=middle-1;
else
begin=middle+1;
}
i=pos-1;
while(i>=begin){
a[i+1]=a[i];
--i;
}
a[begin] = key;
}
}
三、希尔排序
Shell sort，递减增量排序算法，因DL．Shell于1959年提出⽽得名，是插⼊排序的⼀种更⾼效的改进版本。
核⼼：增量分组+插⼊排序+增量递减
描述：希尔排序是⾮稳定排序算法，希尔排序的时间复杂度与增量序列的选取有关，希尔增量时间复杂度为O(n^2)。
步骤：
1、先取⼀个⼩于n的整数d1作为第⼀个增量，把⽂件的全部记录分组。所有距离为d1的倍数的记录放在同⼀个组中，在各组内进⾏直接插⼊排序。
2、取第⼆个增量d2<d1重复上述的分组和排序，
3、直⾄所取的增量dt=1(dt<dt-l<…<d2<d1)，即所有记录放在同⼀组中进⾏直接插⼊排序为⽌。
上图：
伪代码
[cpp] view plain copy
input: an array a of length n with array elements numbered 0 to n − 1
inc ← round(n/2)
while inc > 0do:
for i = inc .. n − 1do:
temp ← a[i]
j ← i
while j ≥ inc and a[j − inc]> temp do:
a[j] ← a[j − inc]
j ← j − inc
a[j] ← temp
inc ← round(inc / 2)
实现：
[cpp] view plain copy
#include <assert.h>
#include <iostream>
#include <algorithm>
#include <iterator>
using namespace std;
void shell_sort(int *a,int len){
assert(a!=NULL && len>0);
int key=0;
for(int gap=len/2;gap>0;gap/=2){
for(int i=gap;i<len;++i){
key=a[i];
int j=i-gap;
while(j>=0 && a[j]>key){
a[j+gap]=a[j];
j-=gap;
}
a[j+gap]=key;
}
}
int main(){
int seq[]={3,7,8,5,2,1,9,5,4};
int length=sizeof(seq)/sizeof(int);
copy(seq,seq+length,ostream_iterator<int>(cout,""));
cout<<endl;
cout<<"begin: "<<endl;
shell_sort(seq,length);
cout<<"end: "<<endl;
copy(seq,seq+length,ostream_iterator<int>(cout,""));
cout<<endl;
return0;
}
结果
四、选择排序
Selection sort是⼀种简单直观的排序算法。
描述：将⽆序区的最值放在有序区的末尾，以此对序列进⾏排序最好、平均和最坏运⾏时间为θ(n^2)。
算法步骤为：（此处为递减序列，递增则选⽆序区的最⼤值）
1、初始状态：⽆序区为]，有序区为空。
2、第i趟排序开始时，当前有序区和⽆序区分别为R[1..i-1]和R[i…n]。该趟排序从当前⽆序区中选出关键字最⼩的记录R[k]，将它与⽆序区的第1个记录R交换，使R[1..i]和R分别变为记录个数增加1个的新有序区和记录个数减少1个的新⽆序区。
3、前n-1趟结束，数组有序化了
上图：
伪代码为：
[cpp] view plain copy
SELECTION-SORT(A)
for j = 1 to Length(A)
i = j
key = A(i)
for i to Lenth(A)
if key>A(i)
key = A(i)
k = i
A(k) = A(j)
A(j)  = key
实现：
[cpp] view plain copy
#include <assert.h>
#include <iostream>
#include <algorithm>
#include <iterator>
using namespace std;
void select_sort(int *a,int len){
assert(a!=NULL && len>0);
int max=0,pos=0;
for(int i=0;i<len;++i){
max=a[i];
pos=i;
for(int j=i;j<len;++j){
if(a[j]>max){
pos=j;
max=a[j];
}
}
swap(a[i],a[pos]);
}
}
int main(){
int seq[]={3,7,8,5,2,1,9,5,4};
int length=sizeof(seq)/sizeof(int);
copy(seq,seq+length,ostream_iterator<int>(cout,""));
cout<<endl;
cout<<"begin: "<<endl;
select_sort(seq,length);
cout<<"end: "<<endl;
copy(seq,seq+length,ostream_iterator<int>(cout,""));
cout<<endl;
return0;
}
结果：
五、归并排序
《算法导论》的第2章介绍了归并排序及其算法分析，并引⼊了分治算法策略，divide-and-conquer。
核⼼：分治
描述：指的是将两个已经排序的串⾏合并成⼀个串⾏的操作。最坏情况下运⾏时间为θ(n^2)，但是平均性能相当好，期望的运⾏时间为θ(nlgn)。
算法步骤为：
1、        Divide: 把长度为n的输⼊序列分成两个长度为n/2的⼦序列
2、        Conquer: 对这两个⼦序列分别采⽤归并排序
3、        Combine: 将两个排序好的⼦序列合并成⼀个最终的排序序列。
上图：
伪代码为：
[cpp] view plain copy
MERGE（A，p,q,r）
N1←q-p+1
N2←r-q
Creat arrays L[1……n1+1] and R[1….n2+1]
For i←1 to n1
Do l[i]←A[p+i-1]
For j←1 to n2
Do R[j]←A[q+j]
L[n1+1]←∞
R[n2+1]←∞
i←1
j←1
for k←p to r
do if Li]<=R[j]
then A[k]←l[j]
i←i+1
else A[k]←R[j]
j←j+1
NERGE_SORT(A,p,r)
If p<r
Then q←[(p+r)/2]
MERGE_SORT(A,p,q)
MERGE_SORT(A,p+1,q)
实现
[cpp] view plain copy
#include<assert.h>
#include<iostream>
#include<algorithm>
#include<iterator>
usingnamespace std;
//combinea[begin,middle] with a[middle+1,end]
voidcombine_array(int *a,int b,int m,int e,int *temp){
assert(a!=NULL && b>=0 &&m>=0 && e>=0 && temp!=NULL);
int i=b,j=m+1,pos=0;
while(i<=m && j<=e){
if(a[i]<=a[j])
temp[pos++]=a[i++];
else
temp[pos++]=a[j++];
}
while(i<=m)
temp[pos++]=a[i++];
while(j<=m)
temp[pos++]=a[j++];
for(i=0;i<pos;++i){
a[b+i]=temp[i];
}
}
voidmerge_sort(int *a,int begin,int end,int *temp){
assert(a!=NULL && begin>=0&& end>=0 && temp!=NULL);
if(begin<end){
int middle = (begin+end)/2;
merge_sort(a,begin,middle,temp);//left
merge_sort(a,middle+1,end,temp);//rigth
combine_array(a,begin,middle,end,temp);//combine
}
}
int main(){
int seq[]={3,7,8,5,2,1,9,5};
int length=sizeof(seq)/sizeof(int);
int *t = new int(length);
copy(seq,seq+length,ostream_iterator<int>(cout,""));
cout<<endl;
cout<<"begin: "<<endl;
merge_sort(seq,0,length-1,t);
cout<<"end: "<<endl;
copy(seq,seq+length,ostream_iterator<int>(cout,""));
cout<<endl;
delete t;
return0;
}
结果：
六、冒泡排序
Bubble sort是⼀种简单的排序算法。⾛访数列的⼯作是重复地进⾏直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越⼩的元素会经由交换慢慢“浮”到数列的顶端。核⼼：⽐⼤⼩
描述：冒泡排序是与插⼊排序拥有相等的执⾏时间。最优O(n)，平均、最初O(n^2)。
步骤
1、⽐较相邻的元素。如果第⼀个⽐第⼆个⼤，就交换他们两个。
2、对每⼀对相邻元素作同样的⼯作，从开始第⼀对到结尾的最后⼀对。这步做完后，最后的元素会是最⼤的数。
3、针对所有的元素重复以上的步骤，除了最后⼀个。持续每次对越来越少的元素重复上⾯的步骤，直到没有任何⼀对数字需要⽐较。
上图
伪代码
[cpp] view plain copy
function bubblesort (A : -1]) {
var inti, j;
for i fromn-1 downto 0 {
for j from0 to i {
if(A[j] > A[j+1])
swap(A[j], A[j+1])
}
}
}
实现
[cpp] view plain copy
#include<assert.h>
#include<iostream>
#include<algorithm>
#include<iterator>
usingnamespace std;
voidbubble_sort(int *a,int len){
assert(a!=NULL && len>0);
for(int i=0;i<=len-1;++i){
for(int j=0;j<=len-1-i;++j)
if(a[j]>a[j+1])
swap(a[j],a[j+1]);
}
}
int main(){
int seq[]={3,7,8,5,2,1,9,5,4};
int length=sizeof(seq)/sizeof(int);
copy(seq,seq+length,ostream_iterator<int>(cout,""));
cout<<endl;
cout<<"begin: "<<endl;
bubble_sort(seq,length);
cout<<"end: "<<endl;
copy(seq,seq+length,ostream_iterator<int>(cout,""));
return0;
}
结果
七、快速排序
算法导论的第七章介绍了快速排序及其算法分析。
核⼼：分治+递归
描述：快速排序采⽤的是分治算法思想，分⽽治之，各个击破。最坏情况下运⾏时间为θ(n^2)，但是平均性能相当好，期望的运⾏时间为θ(nlgn)。算法步骤为：
1、pivot：从数列中挑出⼀个元素作为基准
2、partition：重新排序数列，所有元素⽐基准值⼩的摆放在基准前⾯，所有元素⽐基准值⼤的摆在基准的后⾯（相同的数可以到任⼀边）。
3、recursive：把两个⼦序列递归排序
上图：
伪代码为：
[cpp] view plain copy
function quicksort(q)
var list less,pivotList, greater
if length(q) ≤ 1 {
return q
} else {
select a pivot value pivotfrom q
for each x inq except the pivot element
if x < pivot thenadd x to less
if x ≥ pivot thenadd x to greater
add pivot topivotList
returnconcatenate(quicksort(less), pivotList, quicksort(greater))
}
实现：快排的基准值可以以多种⽅式获得。取⾸元素，末尾元素，或者⼲脆来个随机取值。
维基的百科的实现⾮常经典，代码如下
[cpp] view plain copy
struct Range{
explicit Range(int s=0,int e=0):start(s),end(e){}
int start,end;
};
void quicksort(int n,int arr[]){
if(n<=0) return;
stack<Range> st;
st.push(Range(0,n-1));
while(!st.empty()){
Range range = st.top();
st.pop();
int pivot = d];
int pos = range.start-1;
for(int i=range.start;i&d;++i){
if(arr[i]<pivot){
std::swap(arr[i],arr[++pos]);
}
}
std::swap(arr[++pos],d]);
if(pos-1>range.start){
st.push(Range(range.start,pos-1));
}
if(pos+1&d){
st.push(Range(pos+d));
}
}
}
⾃⼰的实现代码，加了个判断，相等就不交换：
[cpp] view plain copy
#include<assert.h>
#include<iostream>
#include<algorithm>
#include<iterator>
usingnamespace std;
voidquick_sort(int *a,int len){
assert(a);
int pivot=0,low=0,pos=0;
if(len>1){
pivot = a[len-1];
for(pos=0,low=0;pos<len-1;++pos){
if(a[pos]<pivot){
if(a[pos]==a[low]){
++low;
continue;
}
swap(a[pos],a[low++]);
}
}
swap(a[low],a[len-1]);
quick_sort(a,low);
quick_sort(a+low+1,len-low-1);
}
}
int main(){
int seq[]={3,7,8,5,2,1,9,5,4};
int length=sizeof(seq)/sizeof(int);
copy(seq,seq+length,ostream_iterator<int>(cout,""));
cout<<endl;
quick_sort(seq,length);
copy(seq,seq+length,ostream_iterator<int>(cout,""));
cout<<endl;
return0;
}

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。