经典排序算法 - JackPeng博客
source link: http://yuanfentiank789.github.io/2016/06/29/sort/
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
排序的基本概念与分类
排序的定义
假设含有n个记录的序列为{r1,r2,……,rn}，其相应的关键字分别为{k1,k2,……,kn}，需确定1,2,……,n的一种排列p1,p2,……,pn，使其相应的关键字满足kp1<=kp2<=……<=kpn（非递增或非递减）关系，即使得序列成为一个按关键字有序的序列{rp1,rp2,……,rpn}，这样的操作称为排序。
“注意我们在排序问题中，通常将数据元素称为记录。显然我们输入的是一个记录集合，输出的也是一个记录集合，所以说，可以将排序看成是线性表的一种操作。”
“排序的依据是关键字之间的大小关系，那么，对同一个记录集合，针对不同的关键字进行排序，可以得到不同序列。”
“这里关键字ki可以是记录r的主关键字，也可以是次关键字，甚至是若干数据项的组合。比如我们某些大学为了选拔在主科上更优秀的学生，要求对所有学生的所有科目总分降序排名，并且在同样总分的情况下将语数外总分做降序排名。”比较土的办法是先按总分排序，总分相同再按语数外总分降序，“我们还可以应用一个技巧来实现一次排序即完成组合排序问题，例如，把总分与语数外都当成字符串首尾连接在一起（注意语数外总分如果位数不够三位，需要在前面补零），很容易可以得到令狐冲的“753229”要小于张无忌的“753236”，于是张无忌就排在了令狐冲的前面。”
“多个关键字的排序最终都可以转化为单个关键字的排序，因此，我们这里主要讨论的是单个关键字的排序。”
排序的分类
排序的稳定性
假设关键字ki=kj(i!=j)，且在排序前的序列中ri领先于rj，如果排序后ri仍然领先于rj，则称所用的排序方法是稳定的；反之，若可能使得排序后的序列中rj领先ri，则称所用的方法是不稳定的。简单的说，小明和小芳的总分相等，排序前小明排在小芳前面，则排序后小明也在小芳前面，则称排序算法是稳定的，否则算法是不稳定的。
内排序和外排序
内排序是在整个排序过程中，待排序的所有记录全部放置在内存中。外排序是由于排序的记录个数太多，不能同时放置在内存，整个排序过程需要在内外寸之间多次交换数据才能进行。 内排序主要受3个方面的影响。
（1）时间性能。在内排序中，主要进行两种操作：比较和移动。总之在排序过程中要尽可能的减少比较的次数，尽可能的减少移动的次数。
(2)辅助空间。存放待排序的数据所需的空间以及执行算法时所需要的其他存储空间。
（3）算法的复杂性。这里指算法本身的复杂度，而不是算法的时间复杂度。显然算法过于复杂也会影响排序的性能。
“下边一共要讲解七种排序的算法，按照算法的复杂度分为两大类，冒泡排序、简单选择排序和直接插入排序属于简单算法，而希尔排序、堆排序、归并排序、快速排序属于改进算法。后面我们将依次讲解。”
由于排序过程多处用到数组两个元素的交换，封装成交换方法如下：
private static void swap(int[] data, int i, int j)
{
data[i] = data[i] + data[j];
data[j] = data[i] - data[j];
data[i] = data[i] - data[j];
}
冒泡排序也叫交换排序，它的基本思想是：两两比较相邻记录的关键字，如果他们顺序错误就把他们交换过来。这个算法的名字由来是由于越小的元素会经过交换慢慢浮到数列的顶端。
初级冒泡排序
private static void bubbleSort(int[] sortable)
{
for (int i = 1; i < sortable.length; i++) {// 需要length-1轮排序
for (int j = 0; j < sortable.length - i; j++) {// 一轮排序,第i轮比较至倒数第i个元素就可以了，
if (sortable[j] > sortable[j + 1]) {// 把最大值放到数组最后
swap(sortable, j, j + 1);
}
}
}
}
如果进行一次循环后，没有任何数据进行交换，则说明此序列已经有序，无需再进行后面的循环判断了。
/**
* 冒泡改进：如果某一轮比较中没有发生交换，则提前退出
*
* @param sortable
*/
private static void bubbleSort(int[] sortable)
{
boolean flag = true;
for (int i = 1; i < sortable.length & flag; i++) {// 需要length-1轮排序
flag = false;
for (int j = 0; j < sortable.length - i; j++) {// 一轮排序,第i轮比较至倒数第i个元素就可以了，
if (sortable[j] > sortable[j + 1]) {// 把最大值放到数组最后
swap(sortable, j, j + 1);
flag = true;
}
}
}
}
“冒泡排序复杂度分析”
对优化后的代码分析，若排序的本身是正序排列（从小到大排列），则只需做n-1次比较，无需交换（最好情况）。若本身为反序排列（从大到小排列），则需做n(n-1)/2次比较，而且需做n(n-1)/2次交换（最坏情况）。因此，总的时间复杂度为O(n2)。
冒泡排序，是不断的在进行比较，若小，则交换，而简单选择排序，是在一个循环比较完成后，取到最小（大）值才交换一次，交换次数比冒泡排序要少。
/**
* 选择排序法 每一轮循环从待排序记录中查找最小（大）值与首元素交换
*
* @param sortable
*/
private static void selectSort(int[] sortable)
{
for (int i = 0; i < sortable.length; i++) {
int minumIndex = i, temp;
for (int j = i + 1; j < sortable.length; j++) {// 取最小值
if (sortable[j] < sortable[minumIndex]) {
minumIndex = j;
}
}
if (minumIndex != i) {// 说明最小值的索引发生了变化，每轮交换一次
swap(sortable, minumIndex, i);
}
}
}
选择排序复杂度分析
从简单选择排序的过程来看，它最大的特点就是交换移动数据次数相当少，这样也就节约了相应的时间。分析它的时间复杂度发现，无论最好最差的情况，其比较次数都是一样的多，第i趟排序需要进行n-i次关键字的比较，此时需要比较sigma(i=1, n-1, n-i)=(n-1)+(n-2)+…+1=n(n-1)/2次。而对于交换次数而言，当最好的时候，交换为0次，最差的时候，也就初始降序时，交换次数为n-1次，基于最终的排序时间是比较与交换的次数总和，因此，总的时间复杂度依然为O(n2)。
应该说，尽管与冒泡排序同为O(n2)，但简单选择排序的性能上还是要略优于冒泡排序。
直接插入排序
初始化：取待排序中的第一个元素为为有序表，除了第一个元素的所有元素组成无序表。
直接插入排序是由两层嵌套循环组成。外层循环标识并决定待插入到有序数列的元素。内存循环为待插数值确定其合适位置，是插入后有序序列仍为有序序列。
外层循环从第2个数值开始。
内层循环中，待插入数值和它左面第1个数值比较，若左面第1个数值比它大，则左面第1个数值放到其后面的位置中（即带插入数值的位置，所以用temp保存一下待插值），然后和左面第2个比较，否则将待插入值放到它左面第1个数值的右面。依次类推。
/**
* 插入排序：类似冒泡排序，每次取一待排数据，一次比较插入前方已经排好顺序的适当位置
*
* @param sortable
*/
private static void insertSort(int[] sortable)
{
for (int i = 1; i < sortable.length; i++) {
int insertNode = sortable[i];// 从1开始，取一个数据元素
for (int j = i - 1; j >= 0 && sortable[j] > insertNode; j--) {// j>=0一定要在前边，
sortable[j + 1] = sortable[j];// 把大于insertNode的元素后移一位，
sortable[j] = insertNode;
}
}
}
复杂度仍然是:O(n2)
归并排序就是利用归并的思想实现的排序方式。他的原理是假设初始序列含有n个记录，则可以看成是n个有序的子序列，每个子序列的长度是1，然后两两合并，得到[n/2]（[x]表示不小于x的最小整数）个长度为2或1的有序子序列；再两两归并，……，如此重复，直至得到一个长度为n的有序序列为止，这种排序方法称为2路归并排序。
/**
* 归并排序 { 49, 97, 38, 13, 27, 50, 76, 65 }
*
* @param sortable
* @param start
* @param end
*/
private static void mergeSort(int[] sortable, int start, int end)
{
if (start >= end)
return;
int center = (start + end) / 2;
// 对左边数组进行递归
mergeSort(sortable, start, center);
// 对右边数组进行递归
mergeSort(sortable, center + 1, end);
// 合并
merge(sortable, start, center, end);
}
/**
* 归并排序 [1, 3, 6, 8, 2, 5, 7, 9] 二路归并 合并两个有序序列
*
* @param sortable
* 数组对象 由两个有序序列组成
* @param start
* 左数组的第一个元素的索引
* @param middle
* 左数组的最后一个元素的索引，middle+1是右数组第一个元素的索引
* @param end
* 右数组最后一个元素的索引
*/
private static void merge(int[] sortable, int start, int middle, int end)
{
int[] tmpArr = new int[sortable.length];
int left = start, right = middle + 1;
int index = start;
for (; left <= middle && right <= end;) {
if (sortable[left] <= sortable[right]) {
tmpArr[index++] = sortable[left++];
} else {
tmpArr[index++] = sortable[right++];
}
}
while (left <= middle) {
tmpArr[index++] = sortable[left++];
}
while (right <= end) {
tmpArr[index++] = sortable[right++];
}
while (start <= end) {
sortable[start] = tmpArr[start++];
}
System.out.println(Arrays.toString(tmpArr));
System.out.println(Arrays.toString(sortable));
System.out.println("========================");
}
快速排序(QuickSort)是冒泡排序的优化算法。 基本思想：通过一趟排序将待排记录分割成独立的两部分，其中一部分记录的关键字比另一部分记录的关键字小，则可以分别对这两部分记录继续进行快速排序，以达到整个序列有序的目的。 枢轴（pivot)：选取待排序列当中的一个关键字，然后想尽办法把它放到一个位置，使得它左边的值都比它小，右边的值都比它大，我们将这样的关键字成为枢轴（pivot)。
一般取待排序最左端的那个关键字为枢轴。
/**
* 快速排序法 { 27, 13, 38, 49, 50, 65, 76, 97 }
*
* @param sortable
* @param low
* @param high
*/
private static void quickSort(int[] sortable, int low, int high)
{
if (low >= high)// 递归退出条件
return;
int pivot = sortable[low];// 通常取第一个元素作为比较对象
int start = low;
int end = high;
while (start < end) {
while (start < end && sortable[end] > pivot) {// 如果end指向的数据大于比较对象，直接跳过
end--;
}
// start<end不成立或sortable[end] > pivot不成立
if (start < end) {// sortable[end] > pivot不成立,则和比较对象交换，并右移start
sortable[start] = sortable[end];
// sortable[end] = pivot;
start++;
}
while (start < end && sortable[start] < pivot) {// 如果start指向的数据小于比较对象，直接跳过
start++;
}
// start<end不成立或sortable[start] < pivot不成立
if (start < end) {// sortable[start] < pivot不成立,则和比较对象交换，并左移end
sortable[end] = sortable[start];
// sortable[start] = pivot;
end--;
}
}
sortable[start] = pivot;// start=end为比较元素最后位置
System.out.println(Arrays.toString(sortable));
quickSort(sortable, low, start - 1);
quickSort(sortable, start + 1, high);
}
快速排序复杂度分析
最优情况：每次分割成两部分都很均匀，即两部分的数据相差不多。仅需递归logn次，算法时间复杂度为O(nlogn) 最坏情况：待排序为正序或反序，每次分割，都是一边为空，需要执行n-1次递归调用，且第i次划分需要经过n-i次的比较，因此比较次数为n-1+n-2+…+1=n(n-1)/2。其时间复杂度为O(n2)。 平均情况： 复杂度为O(nlogn)； 快速排序是不稳定的排序。
“我们根据将排序记录是否全部被放置在内存中，将排序分为内排序与外排序两种，外排序需要在内外存之间多次交换数据才能进行。我们本章主要讲的是内排序的算法。
根据排序过程中借助的主要操作，我们将内排序分为：插入排序、交换排序、选择排序和归并排序四类。之后介绍的7种排序法，就分别是各种分类的代表算法。”
“事实上，目前还没有十全十美的排序算法，有优点就会有缺点，即使是快速排序法，也只是在整体性能上优越，它也存在排序不稳定、需要大量辅助空间、对少量数据排序无优势等不足。因此我们就来从多个角度来剖析一下提到的各种排序的长与短。
我们将7种算法的各种指标进行对比，如表9-10-1所示。”
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK