经常使用排序算法实现[交换排序之冒泡排序、高速排序]

petrel919

　　相关知识

1. 稳定排序和非稳定排序：

稳定排序算法会按照相等的关键（换言之就是值）维持纪录的相对次序。

假设排序算法是稳定的，就是当有两个有相等关键的纪录R和S，且在原本的列表中R出如今S之前，在排序过的列表中R也将会是在S之前。
　　

2. 内排序和外排序

在排序过程中，全部须要排序的数都在内存。并在内存中调整它们的存储顺序。称为内排序。

在排序过程中，仅仅有部分数被调入内存，并借助内存调整数在外存中的存放顺序排序方法称为外排序。

3.算法分类

排序算法从理论上分为例如以下几类：

(1) 交换排序法: 冒泡排序、高速排序等

(2) 选择排序法: 选择排序、堆排序、循环排序等

(3) 插入排序法: 插入排序、希尔排序、二叉查找树排序等

(4) 归并排序法: 归并排序、Strand排序等

(5) 分布排序法: 基数排序、桶排序、计数排序等。

(6) 混合排序法: 反移排序、Tim排序等

以下主要针对常见的排序算法进行分析
　　一：冒泡排序

算法思想：两两比較待排序记录的keyword，发现两个记录的次序相反时即进行交换，直到没有反序的记录为止。

                    能够分为“大数沉底法”和“小数上浮法”两种不同的形式。
　　

时间复杂度：O(n^2)

稳定性：        稳定排序

算法实现：

(1)大数沉底法

void bubble_sort(int array[], int n)
{
int i, j, temp;
for(i = 0; i < n-1; i++)
{
for(j = 0; j < n -i; j++)
{
if(array[j] > array[j+1])
{
temp = array[j];
array[j] = array[j+1];
array[j+1] = temp;
}
}
}
}
　　(2)小数上浮法

void bubble_sort(int array[], int n)
{
int i, j, temp;
for(i = 0; i < n-1; i++)
{
for(j = n - 1; j > i; j--)
{
if(array[j] < array[j-1])
{
temp = array[j];
array[j] = array[j-1];
array[j-1] = temp;
}
}
}
}
　　(3)改进算法
　　若在某一趟排序中未发现有位置的交换。则说明待排序的无序区均满足轻者在上，重者在下的原则，因此。冒泡排序过程可在此趟排序后终止。
　　因此，改进的算法中，引入一个布尔量exchange。在每趟排序開始前。先将其置为0。若排序过程中发生了交换，则将其置为1。
　　各趟排序结束时检查exchange，若未曾发生过交换则终止算法，不再进行下一趟排序。

//array[0 .. n-1]是待排序的文件，採用自上向下扫描。对array做冒泡排序
void bubble_sort(int array[], int n)
{
int i, j, temp;
int exchange = 0; //交换标志
for(i = 0; i < n-1; i++) //最多做n-1趟排序
{
exchange = 0; //本趟排序開始前，交换标志应为假
for(j = 0; j < n - i; j++) //对当前无序区array[0 .. n-i]自上向下扫描
{
if(array[j] > array[j+1])
{
temp = array[j];
array[j] = array[j+1];
array[j+1] = temp;
exchange = 1;  //发生了交换。故将交换标志置为真
}
}
if(!exchange) //本趟排序未发生交换。提前终止算法
return;
}
}
　　二：高速排序

算法思想：通过一趟排序将要排序的数据切割成独立的两部分，当中一部分的全部数据都比另外一部分的全部数据都要小，然后再按此方法对这两部分数据分别进行高速排序。整个排序过程能够递归进行，以此达到整个数据变成有序序列。

时间复杂度：O(nlog2n)

稳定性：        不稳定排序

算法实现：

void quick_sort(int s[], int low, int high)
{
if (low < high)
{
int i = low, j = high, x = s[low];
while (i < j)
{
while(i < j && s[j] >= x) // 从右向左找第一个小于x的数
j--;  
if(i < j)
s[i++] = s[j];
while(i < j && s < x) // 从左向右找第一个大于等于x的数
i++;  
if(i < j)
s[j--] = s;
}
s = x;  /*一遍扫描完后，放到适当位置*/  
quick_sort(s, low, i - 1);  /*对基准点左边的数再运行高速排序*/  
quick_sort(s, i + 1, high); /*对基准点右边的数再运行高速排序*/  
}
}