内部排序之---交换类排序

二：交换类排序
1：冒泡排序（相邻比序列）
【算法思想】反复扫描待排序记录序列，它是通过相邻的数据元素的交换，逐步将待排序序列编程有序列的过程。
eg:以升序为例子：在第一趟冒泡排序中，从第一个记录开始，扫描整个排序记录，若相邻的两个序列逆序，就交换位置。在扫描过程中，不断的将相邻两个记录中较大的记录向后移动，最后必然将待排序列中最大的关键字换到待排序的末尾，这也是最大关键字应该在的位置。然后第二趟冒泡排序，对前n-1个序列进行同样的操作。依次，知道没有发现一个逆序。所以冒泡过程最多进行n-1趟
【过程】
A：48   62    35   77   55   14   35   98   22   40
48与62比较，不变，62与35比较，交换，62与77比较，不变，77与55比较交换，77与14比较，交换，77与35比较，交换，77与98比较，不变，98与22比较，交换，98与44比较交换----------得出最大序列    98
B：48    35   62   55   14   35   77   22   40   98
仍然想A一样，依次类推得出第二大序列   77，依次排序
附上算法：

Void Bubblesort(int r[],int len)
{
Int n=len;
Int change=1;
Int i,j;
for(i=1;i<=n;i++)
{change=0;
for(j=1;j<=n-i;j++)
{
if(r[j]>r[j+1])
r[0]=r[j];
r[j]=r[j+1];
r[j+1]=r[0];
change=1;
}
}

【算法分析】冒泡排序算法的最坏情况是待排序记录按照关键字的逆序排列，此时，每一编冒泡排序得进行i次比较，3i次移动，经过n-1次冒泡排序后，总的移动次数是2n(n-1)/2.该算法的时间复杂度为O(n^2),空间复杂度为O(1)
2:快速排序
--------越乱效果越好，越整齐，效果越差
【算法思想】从待排序记录序列中选择一个记录，其关键字设为K，然后将其余关键字小于K的记录移动到前面，而将关键字大于K的记录移动到后面，结果将待排序记录序列分为两个表，通过一次划分后，就以关键字K的记录为界限，我们将这个过程称作一趟快速排序。
【过程】
假设待划分序列为r[left],r[left+1],...r[right],具体实现上述划分的时候，可以设有两个指针i和j，初值分别为left和right。首先将基准记录r[left]移动至变量r[0]中，是r[left]相当与空单元，然后反复进行如下两个扫描过程，直到i和j相遇。
（1）    j从右边向左扫描，直到r[j]
（2）    i从左向右扫描，直到r[i]>r[0],将r[i]移动到空单元r[j],此时r[i]相当与空单元。
     当i与j相遇的时候，r[i](或者r[j])相当与空单元，且r[i]左边所有记录的关键字均不大于基准记录的关键字，而r[i]右边所有记录的关键字均不小于基准记录的关键字。最后将基准记录移动到r[i]，就完成了一次划分。
A：48  62   35   77   55   14   35   98
r[0]=48,i=1,low=1,high=8,发现98>48则不变，high=7,r[high]=35,与r[0]比较，r[0]>r[7]交换，r[1]=35,r[7]为空。接着low+1,r[low]=r[2]与r[0]比较，发现r[0]r[0]，然后将r[low]放到r[6]=r[low]=77，然后high=high-1=5,r[high]=55>r[0],接着high=high-1=4,i与j相等。将此位置r[4]设置为r[0]的值。
依次的结果是：
35    14   35   48   55   77   62   98
B：剩下的每次排序都与第一次一样。
附上算法代码：

Void quckpass(int r[],int left,int right)
{
Int low=left;
Int high=right;
r[0]=r[low];
while(low<high)
{
    while(low<high&&r[high]>r[0])
high—;
    if(low<high)
{
r[low]=r[high];
low++;
}
while(low<high&&r[low]<r[0])
    low++;
if(low<high)
{
    r[high]=r[low];
    high--;
}
}
r[low]=r[0];
return low;
}
Void qucksort(int r[],int low,int high,int len)
{
    Int pos;
    if(low<high)
{
    pos=quckpass(r,low,high);
    qucksort(r,low,high-1,len);
    qucksort(r,low+1,high,len);
}
}

【算法分析】
(1)    快速排序的最好情况是每趟将序列一分两半，正好在表中间。将表分为两个大小相等的子表，类似于折半查找 时间复杂度T（n）=O(nlog2n)
(2)    快速排序的最差情况是已经排好序列，第一汤经过n-1次比较，第1个记录定在原味值，左部子表为空表，右部子表为N-1个记录，第二趟n-1个记录经过n-2 次比较，第2个记录定在原位置，左部子表为空，右部子表为n-2个记录，依次需要比较次数为n^2/2
(3)    快速排序的空间复杂度为：O(log2n).