一、快速排序
1、定义
快速排序是对冒泡排序的一种改进。其基本思想是：通过一趟排序将待排序记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。
2、举例
对“6 1 2 7 9 3 4 5 10 8”进行排序。
首先在这个序列中找一个数作为关键字（枢轴）。为了方便，选取第一个数6作为关键字。
之后要将这个序列中所有比关键字6大的数放在它的右边，比关键字6小的数放在它的左边，类似下面这种排列：3 1 2 5 4 6 9 7 10 8
3、算法思想
使用两个变量i（哨兵i）和j（哨兵j），分别指向序列最左边（即i=1）和最右边（即=10）。
image.png
首先哨兵j开始移动（因为此处设置的基准数是最左边的数，所以需要让哨兵j先移动）。哨兵j一步一步地向左挪动（即j--），直到找到一个小于6的数停下来。接下来哨兵i再一步一步向右挪动（即i++），直到找到一个数大于6的数停下来。最后哨兵j停在了数字5面前，哨兵i停在了数字7面前。然后交换哨兵i和哨兵j所指向的元素的值。
image.png
交换之后的序列如下：
image.png
第一次交换结束。接下来开始哨兵j继续向左挪动（每次必须是哨兵j先出发）。找到4（比关键字6要小，满足要求）之后停了下来。哨兵i也继续向右挪动的，找到9（比关键字6要大，满足要求）之后停了下来。此时再次进行交换。
image.png
交换之后的序列如下：
image.png
第二次交换结束。哨兵j继续向左挪动，找到3（比关键字6要小，满足要求）之后又停了下来。哨兵i继续向右移动，此时哨兵i和哨兵j相遇了，都走到了3的位置。此时查找结束。将6和3进行交换。
image.png
交换之后的序列如下：
image.png
到此第一轮排序结束。此时以关键字6为分界点，6左边的数都小于等于6，6右边的数都大于等于6。以6为分界点拆分成了两个序列，左边的序列是“3 1 2 5 4”，右边的序列是“9 7 10 8”。接下来按照上面的方法分别处理这两个序列。
image.png
4、与冒泡相比
快速排序比冒泡排序快，因为每次交换是跳跃式的。每次排序的时候设置一个关键字，将小于等于关键字的数全部放到关键字的左边，将大于等于关键字的数全部放到关键字的右边。这样在每次交换的时候就不会像冒泡排序一样每次只能在相邻的数之间进行交换，交换的距离大的多。因此总的比较和交换次数就少了，速度就提高了。最坏的情况是逆序(如9 8 7 6 5), 算法会重复一个过程: 不停地往左冒一个最大值, 往右沉一个最小值, 这样就会退化成O(n2)。因此快速排序的最差时间复杂度和冒泡排序是一样的都是O(n2)，它的平均时间复杂度为O(nlogn)。快速排序是基于“二分”的思想。
5、算法
void quicksort(int left,int right) {
int i,j,t,temp;
if(left>right)
return;
temp=a[left]; //temp中存的是关键字
i=left;
j=right;
while(i!=j) {
//顺序很重要，要先从右边开始找
while(a[j]>=temp && i<j)
j--;
//再找右边的
while(a[i]<=temp && i<j)
i++;
//交换两个数在数组中的位置
if(i<j) {
t=a[i];
a[i]=a[j];
a[j]=t;
}
}
//最终将关键字归位
a[left]=a[i];
a[i]=temp;
quicksort(left,i-1);//继续处理左边的，这里是一个递归的过程
quicksort(i+1,right);//继续处理右边的 ，这里是一个递归的过程
}
二、选择排序
选择排序的基本思想：每一趟在n - i + 1 (i = 1, 2, ..., n - 1)个记录中选取关键字最小的记录作为有序序列中第i个记录。
1、简单选择排序
首先在未排序的序列里找到最小(大)元素，放到序列的首端，再从剩余元素中找到最小(大)的元素，放到序列的尾端。依次循环，直到排序完成。
A.举例
第一趟排序：
原始数据：5， 4， 8， 9， 2， 1
比较一轮，最小的数是1，把1和首位的5互换
结果：1， 4， 8， 9， 2， 5
第二趟排序：
剩余元素里，2最小，把2和剩余元素的首位4交换位置
结果：1， 2， 8， 9， 4， 5
第三趟排序：
剩余元素里，4最小，把4和8交换位置
结果：1， 2， 4， 9， 8， 5
第四趟排序：
剩余元素里，5最小，把5和9交换位置
结果：1， 2， 4， 5， 8， 9
排序完成。
B.算法
public static void selectSort(int[] a, int length) {
int temp;
for(int i = 0; i < length; i++) {
//内层循环j=i+1,外层循环控制着循环次数。
//即每趟中a[i]这个值就是本趟的最小值。i位置上是最小值
for(int j = i + 1; j < length; j++) {
if(a[i]>a[j]) {
temp=a[i];
a[i]=a[j];
a[j]=temp;
}
}
}
}
C.复杂度
时间复杂度：选择排序交换次数在0 ~ (n - 1)次之间，需要比较n(n - 1) / 2次，赋值操作次数在0 ~ 3(n - 1)次之间，因此平均时间复杂度为O(n2)
稳定性：当待排序列中有相等的元素时，排序过程中很可能打乱相等元素的位置，经常会来回交换，因此选择排序是不稳定的排序。
2、树形选择排序
因为简单选择排序没有利用上次选择时比较的结果，所以造成了比较次数多，速度慢。如果能够加以改进，将会提高排序的速度，所以出现了树形选择排序和堆排序。
树形选择排序(Tree Selection Sort)，又称锦标赛排序(Tournament Sort)，是一种按照锦标赛思想进行选择排序的方法。
首先将n个数据元素两两分组，分别按关键字进行比较，得到n／2个比较的优胜者(关键字小者)，作为第一步比较的结果保留下来， 然后对这n／2个数据元素再两两分组，分别按关键字进行比较，如此重复，直到选出一个关键字最小的数据元素为止。这个过程可用一棵有n个叶子结点的完全二叉树表示。
A.举例
原始数据如下：
image.png
叶子节点即是所有的参赛者，两两比较，胜出者参与下一轮，也就是说胜出者上升到父节点。若是参赛者为奇数个，则最后一个参赛者直接晋级，按从小到大排序，小的胜出。
下一趟排序，把胜出者的兄弟节点上升到父节点位置。从此位置向上调整树。过程如下图：
image.png
这一趟排序，我们利用了上一趟的排序信息：8与23比较，8胜出。因此没有进行重复比较，这在元素较多时，效果更加明显。后面的比较以此类推。
B.复杂度
由于含有n个叶子结点的完全二叉树的深度为[log2n]+1，则在树形选择排序中，除了最小关键字以外，每选择一个次小关键字仅需进行[log2n]次比较，因此，它的时间复杂度为O(nlogn)。
但是，这种排序方法也有一些缺点，比如辅助存储空间较多，并且需要和“最大值”进行多余的比较。为了弥补，提出了另一种形式的选择排序——堆排序。
网友评论