面试准备-排序算法

C++面试 免不了要涉及到数据结构，工作几年了这些东西都忘得差不多了，现在只好硬着头皮好好学习了

假设含n个记录的序列为{R1,R2,R3,........Rn}

其对应的关键字序列为{K1,K2,K3,........Kn}

假设Ki=Kj且排序前的序列中Ri领先于Rj，若排序后的序列中Ri仍领先与Rj，则排序算法是稳定的，反之是不稳定的。

冒泡排序、插入排序、归并排序、基数排序是稳定排序

选择排序、快速排序、希尔排序、堆排序是不稳定排序

简单排序方法（时间复杂度位O(n2)）:插入排序、希尔排序

先进的排序方法（时间复杂度为O(nlogn)）

基数排序方法（时间复杂度为O(d*n)）

当序列基本有序或n值较小时，插入排序最佳。

当序列n值很大而关键字较小，基数排序最佳。

最好情况  

简单排序      数据有序      O(n)

在所有同数量级O(nlogn)的排序方法中，快速排序的平均性能最好。

插入排序

方法：在第P趟，将位置P上的元素向左移动到它在前P+1个元素中的正确位置上

算法：

void InsertSort( int A[] ,int N )

{

int tmp = 0;

for( int i=1; i<N; i++)

{

tmp = A[i];

for( int j=i; j>0&&A[j-1]>tmp; j--)

{

A[j] = A[j-1];

}

A[j] = tmp;

}

}

冒泡排序

方法：临近的数字两两比较，按照顺序进行交换，一趟过去之后，最小的交换到最前一位

void Bubble_sort ( int A[] , int N)

{

for( int i=0; i<N; i++)

{

for(  int j=i;  j<N; j++ )

{

if( A[i] > A[j] )

{

temp = a[i];

a[i] = a[j];

a[j] = temp;

}

}

}

}

void BubbleSort(int A[],int n)
{
int tmp = 0;
for( int i=0; i<n; i++)
{
for(int j=0; j<n-1-i;j++)
{
if( A[j] > A[j+1])
{
tmp = A[j];
A[j] = A[j+1];
A[j+1] = tmp;
}
}
}
}

选择排序法

方法：直接从带排序的数组中选择一个最小的数字，顺序放入到新数组中。

void Select_Sort( int A[], int N )

{

for( int i=0; i<N; i++ )

{

min = A[i];

min_index = i;

for( int j=i; j<N; j++)

{

if( min > A[j] )

{

min = A[j] ;

min_index = j;

}

}

if( min_index != i )

{

temp = A[i];

A[i] = A[min_index];

A[min_index] = temp ;

}

}

}

希尔排序

方法：使用一个序列h1,h2,..........ht叫做增量序列，只要ht=1,任何增量序列都可行。

归并排序

方法：将两个或两个以上的有序表组合成一个新的有序表，稳定的排序法。