经过大概一个月的时间，终于数据结构学习进入尾声了，当然我觉得还需要再深入的研究，现在只是看了一遍，理解了，但是离透彻，应用，掌握还有一段距离，所以还需要努力。今天把排序这一章的大部分东西看了一遍，因为比较好实现，所以做一个总结。
交换，根据序列中两个元素关键字的比较结果来对换这两个记录在序列中的位置，主要有冒泡排序和快速排序。听到快排这两个字有木有一种很吊的感觉。
- 冒泡排序
设待排序表长为n，从后往前两两比较相邻元素的值，若为逆序，则交换他们，直到序列比较完，称为一趟冒泡。结果就是最小的元素交换到待排序列的第一个位置。下一趟冒泡时候，前一趟的最小元素将不参与比较。最多n－1趟冒泡就能把元素排好序。
算法实现：
//
// bubblesort.c
// datastructure
//
// Created by 杜光亭 on 16/7/30.
// Copyright © 2016年 Kevin. All rights reserved.
//
#include "bubblesort.h"
#include <stdio.h>
#include <stdlib.h>
#define bool int
#define true 1
#define false 0
//冒泡排序法
void printlist(int a[],int len){
for(int i=0;i<len;i++){
printf("%d->",a[i]);
}
printf("end\n");
}
void swap(int a[],int b,int c){
int tmp = a[b];
a[b] = a[c];
a[c] = tmp;
}
//输入需要拍序的数组
void BubbleSort(int sequence[],int len){
//获取数组长度sizeof必须在数组定义区域才能使用，因为传递过来是数组的指针，是一个地址
//冒泡首先对所有元素进行遍历,除过最后一个元素
for(int i=0;i<len-1;i++){
//定义一个标志，当一次冒泡没有元素发生交换，则说明冒泡完成
printf("handle elem %d\n",i);
bool flag = false;
//从后面到前面进行冒泡
for(int j=len-1;j>i;--j){
//如果前面的值大于后面的，冒泡向前
if(sequence[j-1]>sequence[j]){
swap(sequence,j-1,j);
flag = true;
}
}
if(flag == false){
return;
}
}
}
int main(){
int a[]={46,79,56,38,40,84};
int len = sizeof(a)/sizeof(a[0]);
BubbleSort(a, len);
printlist(a,len);
}```
排序结果：`38->40->46->56->79->84->end`
仅用了常数个辅助单元，空间复杂度为O(l)
最好情况：初始序列有序，比较次数为n-1，移动次数为0，所以时间复杂度为O(n)
最坏情况：初始序列为逆序，n－1趟排序，第i趟排序需要n-i次关键字比较，而且每次比较需要3次移动元素来交换位置，所以比较次数为n(n-1)/2，移动次数为3n(n-1)/2，时间复杂度为 O(n2)，平均时间复杂度也是O(n2)
冒泡排序是一个稳定的排序方法。
2. 快速排序
基本思想是基于分治法，通过一趟排序使得排序表分为两个独立的部分，左侧的小于划分元素，右侧的大于划分元素，划分元素放在了最终位置上，这个过程称为一次快速排序。然后递归的进行上述过程，直到所有元素放在了最终位置上。
算法实现：关于划分元素有两种方法进行实现，貌似第二个方法更好一点。
//
// fastsort.c
// datastructure
//
// Created by 杜光亭 on 16/7/30.
// Copyright © 2016年 Kevin. All rights reserved.
//
include "fastsort.h"
include <stdio.h>
include <stdlib.h>
define bool int
define true 1
define false 0
void printlist(int a[],int len){
for(int i=0;i<len;i++){
printf("%d->",a[i]);
}
printf("end\n");
}
void swap(int a[],int b,int c){
int tmp = a[b];
a[b] = a[c];
a[c] = tmp;
}
//两种划分方法
int partition(int a[],int low,int high){
//严版的划分方法，貌似不能直接搞成有序的
//使用第一个元素作为枢轴点
int pivot = a[low];
//当两个指针没有相遇的时候
while(low < high){
//当出现从右边的指针所确定的值小于pivot时退出循环
while(low<high&&a[high]>=pivot) --high;
//将a[low]和该元素交换
a[low] = a[high];
//开始循环low指针
while(low<high&&a[low]<=pivot) ++low;
//当low指向的值大于pivot时候，交换high指针处的值
a[high] = a[low];
}
//然后将pivot的值置为low
a[low] = pivot;
return low;
}
//另外一种划分方法
int partition2(int a[],int low,int high){
//记录第一个元素
int first = a[low];
//初始化指针位置
int i=low,j=high+1;
//开始循环
while(true){
//j指针遍历,如果值小于first的话退出循环，记录指针位置
while(a[--j]>first) if(i==high) break;
//i指针遍历，如果值大于first的话退出循环,记录指针位置
while(a[++i]<first) if(j==low) break;
//检测指针是否越界
if(i>=j) break;
//这里将两个值进行交换
swap(a,i,j);
}
//最后将第一个元素和j的元素进行交换
swap(a,low,j);
return j;
}
//快速排序
void QuickSort(int a[],int low,int high){
//一个递归函数处理
if(low < high){
//划分操作
int pivotpos = partition(a,low,high);
QuickSort(a, low, pivotpos - 1);
QuickSort(a, pivotpos+1, high);
}
}
void fastSort(int a[],int low,int high){
//一个递归函数处理
if(low < high){
//划分操作
int pivotpos = partition2(a,low,high);
QuickSort(a, low, pivotpos - 1);
QuickSort(a, pivotpos+1, high);
}
}
int main(){
int a[]={46,79,56,38,40,84};
QuickSort(a, 0, 5);
printlist(a, sizeof(a)/sizeof(a[0]));
//第一次的结果是 40->38->46->56->79->84->end
int b[]={46,79,56,38,40,84};
fastSort(b,0,5);
printlist(b,sizeof(b)/sizeof(b[0]));
}```
然后对于同一个序列，第一次快排之后，算法1给出的结果是40->38->46->56->79->84->end，但是算法2给出的结果是38->40->46->56->79->84->end，最终结果。
空间效率，递归需要一个递归工作栈来保存每一层递归调用的必要信息，容量与递归调用的最大深度一致，最好情况是log2(n+1)向上取整。最坏情况是n－1次递归调用，因此栈的深度是O(n)，平均情况下栈的深度是O(log2n)，空间复杂度在最坏情况下是O(n)，平均情况是O(log2n)。
时间效率，最坏情况下是O(n2)，最好情况是O(nlog2n)，快速排序是所有内部排序算法中平均性能最优的排序算法。
但是快速排序不是一个稳定的排序算法。
每一趟的排序后将一个元素放到其最终的位置上。
Tips:
- 待排序数据是基本有序的时候，每次选取第n个元素为基准的时候，会导致划分空间分配不均匀，不利于发挥快速排序算法的优势，当分布较为随机的时候，效率好。所以一般开始算法的时候进行随机乱序。
- 当每次枢轴把表等分为长度相近的两个子表的时候，速度是最快的，当表本身是有序的或者逆序的时，速度最慢。
- 第i趟完成时，将会有i个以上的数出现在将要出现的位置上，最终位置。
- 递归次数与各元素的初始排列有关，如果每次划分后分区比较平衡，那么递归次数比较少。
- 快速排序过程构成一个递归树，递归深度即树的高度，当枢轴值每次都等分时候，树高伟log2n，每次都是最大或者最小值的时候，形成一颗单线树，深度为n。
