排序算法复杂度排序算法( 四 )

首先从后半部分开始，如果扫描到的值大于基准数据就让 high-1 ，如果发现有元素比该基准数据的值小，比如上面的 18 = tmp ，就让 high位置的值赋值给low位置，结果如下：
然后开始从前往后扫描，如果扫描到的值小于基准数据就让 low+1 ，如果发现有元素大于基准数据的值，比如上图 46 = tmp ，就再将 low 位置的值赋值给 high 位置的值，指针移动并且数据交换后的结果如下：
然后再开始从前往后遍历，直到 low=high 结束循环，此时low或者high的下标就是基准数据23在该数组中的正确索引位置，如下图所示：
这样一遍遍的走下来，可以很清楚的知道，快排的本质就是把比基准数据小的都放到基准数的左边，比基准数大的数都放到基准数的右边，这样就找到了该数据在数组中的正确位置。
然后采用递归的方式分别对前半部分和后半部分排序，最终结果就是自然有序的了。
输出结果：
最好情况下快排每次能恰好均分序列，那么时间复杂度就是O(nlogn)，最坏情况下，快排每次划分都只能将序列分为一个元素和其它元素两部分，这时候的快排退化成冒泡排序，时间复杂度为O(n^2) 。
插入排序的基本操作就是将一个数据插入到已经排好序的有序数据中，从而得到一个新的、个数加一的有序数据，算法适用于少量数据的排序，时间复杂度为O(n^2) 。是稳定的排序方法。
将一个数据插入到已经排好序的有序数据中
第一趟排序：
用数组的第二个数与第一个数( 看成是已有序的数据 )比较
第二趟排序：
用数组的第三个数与已是有序的数据 {2,3} (刚才在第一趟排的)比较
在第二步中：
...
后面依此类推
输出结果：
选择排序是一种简单直观的排序算法。它的工作原理是每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到全部待排序的数据元素排完。选择排序是不稳定的排序方法。
举例：数组int[] arr={5,2,8,4,9,1}
第一趟排序：原始数据： 5 2 8 4 9 1
最小数据1，把1放在首位，也就是1和5互换位置，
排序结果： 1 2 8 4 9 5
第二趟排序：
第1以外的数据 {2 8 4 9 5} 进行比较，2最小，
排序结果： 1 2 8 4 9 5
第三趟排序：
除 1、2 以外的数据 {8 4 9 5} 进行比较，4最小，8和4交换
排序结果： 1 2 4 8 9 5
第四趟排序:
除第 1、2、4 以外的其他数据 {8 9 5} 进行比较，5最小，8和5交换
排序结果： 1 2 4 5 9 8
第五趟排序：
除第 1、2、4、5 以外的其他数据 {9 8} 进行比较，8最小，8和9交换
排序结果： 1 2 4 5 8 9
输出结果：
归并排序（merge sort）是利用归并的思想实现的排序方法，该算法采用经典的分治（divide-and-conquer）策略（分治法将问题分(divide)成一些小的问题然后递归求解，而治(conquer)的阶段则将分的阶段得到的各答案"修补"在一起，即分而治之) 。
比如我们对 [8,4,5,7,1,3,6,2] 这个数组进行归并排序，我们首先利用分治思想的“分”将数组拆分。
输出结果：

文章插图
排序算法是怎样的？一、背景介绍
在计算机科学与数学中，排序算法（Sorting algorithm）是一种能将一串资料依照特定排序方式进行排列的一种算法。
最常用到的排序方式是数字顺序以及字典顺序。
有效的排序算法在一些算法（例如搜寻算法与合并算法）中是重要的，如此这些算法才能得到正确解答。
排序算法也用在处理文字资料以及产生人类可读的输出结果。
基本上，排序算法的输出必须遵守下列两个原则：
1、输出结果为递增序列（递增是针对所需的排序顺序而言）；
2、输出结果是原输入的一种排列、或是重组；
虽然排序算法是一个简单的问题，但是从计算机科学发展以来，在此问题上已经有大量的研究。更多的新算法仍在不断的被发明。
二、知识剖析
查找和排序算法是算法的入门知识，其经典思想可以用于很多算法当中。因为其实现代码较短，应用较常见。所以在面试中经常会问到排序算法及其相关的问题。但万变不离其宗，只要熟悉了思想，灵活运用也不是难事。
一般在面试中最常考的是快速排序和冒泡排序，并且经常有面试官要求现场写出这两种排序的代码。对这两种排序的代码一定要信手拈来才行。除此之外，还有插入排序、冒泡排序、堆排序、基数排序、桶排序等。

排序算法复杂度 排序算法( 四 )

秒懂生活扩展阅读

排序算法复杂度排序算法( 四 )