公认最好的排序算法
刘耀文的大沙雕
钟意阿满
的排序方法中，采用哪种方法最好
拿钱让别人替你排！
事实上各种排序方法个有优缺点适用于不同的场合：
排序（Sorting)
插入排序（insertion
sort）:直接插入排序
希尔排序（shell's
sort）(缩小增量排序Diminishing。
increment
sort)
交换排序：冒泡排序（bubble。
sort）快速排序（quick。
sort）
选择排序:直接选择排序（straight。
selection
sort），堆排序；
归并排序（merge
sort）：
分配排序：箱排序（Bin
sort）,基数排序（radix。
sort）
更多的自己研究一下。
排序方法的选取主要考虑算法的性能与资源占用。也就是速度和占用的存储空间。
抱起亚轩找小葵
数据结构中哪种排序方式效率最好
这个各取所需，根据不同的需要选取不同的方法。
我们通常所说的排序算法往往指的是内部排序算法，即数据记录在内存中进行排序。
排序算法大体可分为两种：
一种是比较排序，时间复杂度O(nlogn) ~ O(n^2)，主要有：冒泡排序，选择排序，插入排序，归并排序，堆排序，快速排序等。
另一种是非比较排序，时间复杂度可以达到O(n)，主要有：计数排序，基数排序，桶排序等。
排序算法稳定性的简单形式化定义为：如果Ai = Aj，排序前Ai在Aj之前，排序后Ai还在Aj之前，则称这种排序算法是稳定的。通俗地讲就是保证排序前后两个相等的数的相对顺序不变。
对于不稳定的排序算法，只要举出一个实例，即可说明它的不稳定性；而对于稳定的排序算法，必须对算法进行分析从而得到稳定的特性。需要注意的是，排序算法是否为稳定的是由具体算法决定的，不稳定的算法在某种条件下可以变为稳定的算法，而稳定的算法在某种条件下也可以变为不稳定的算法。
例如，对于冒泡排序，原本是稳定的排序算法，如果将记录交换的条件改成A[i] >= A[i + 1]，则两个相等的记录就会交换位置，从而变成不稳定的排序算法。
其次，说一下排序算法稳定性的好处。排序算法如果是稳定的，那么从一个键上排序，然后再从另一个键上排序，前一个键排序的结果可以为后一个键排序所用。基数排序就是这样，先按低位排序，逐次按高位排序，低位排序后元素的顺序在高位也相同时是不会改变的。
大圣杰锅是
几种常用的排序算法比较
简单排序的算法（直接插入，冒泡，简单选择排序）简单且稳定，适合与待排记录较小的情况，当当待排序的关键码序列已经基本有序时，用直接插入排序最快。
就平均时间的性能而言，快速排序最佳，即排序速度最快，所以在随机情况下，快速排序是最佳选择。一般情况下，快速排序效率最好。
既要节省空间，又要有较快的排序速度，堆排序是最佳选择，其不足之处是建堆时需要消耗较多时间。
若希望排序是稳定的，且有较快的排序速度，则可选用2路归并排序，其缺点需要较大的辅助空间分配。
小韩在追星
常用的排序算法都有哪些？
排序，从小大，0坐标的在下面，即排序后小的在下面，大的在上面。
1，冒泡Bubble：从第0个开始，一直往上，与相邻的元素比较，如果下面的大，则交换。
Analysis：
Implementation：
void BubbleSort(int *pData, int iNum)。
2，插入Insertion：与打扑克牌时整理牌很想象，假定第一张牌是有序的，从第二张牌开始，拿出这张牌来，往下比较，如果有比这张牌大的，则把它拨到上一个位置，直到找到比手上的这张更小的（或到顶了），
则把手上的这张牌插入到这张更小的牌的后面。
Analysis：
Implementation：
void InsertionSort(int *list, int length)。
int i, j, temp;。
for (i = 1; i < length; i++)。
{
temp = list[i];。
j = i - 1;。
while ((j >= 0) && (list[j] > temp))。
{
list[j+1] = list[j];。
j--;。
}
list[j+1] = temp;。
}
3，选择Selection：从所有元素中找到最小的放在0号位置，从其它元素（除了0号元素）中再找到最小的，放到1号位置，......。
Analysis：
Implementation：
void SelectionSort(int data[], int count)。
int i, j, min, temp;。
for (i = 0; i < count - 1; i++) 。
{
/* find the minimum */。
min = i;。
for (j = i+1; j < count; j++)。
{
if (data[j] < data[min])。
{
min = j;。
}
}
/* swap data[i] and data[min] */。
temp = data[i];。
data[i] = data[min];。
data[min] = temp;。
}
4，快速Quick：先拿出中间的元素来（值保存到temp里），设置两个索引（index or pointer），一个从0号位置开始往最大位置寻找比temp大的元素；一个从最大号位置开始往最小位置寻找比temp小的元素，找到了或到顶了，则将两个索引所指向的元素。
互换，如此一直寻找交换下去，直到两个索引交叉了位置，这个时候，从0号位置到第二个索引的所有元素就都比temp小，从第一个索引到最大位置的所有元素就都比temp大，这样就把所有元素分为了两块，然后采用前面的办法分别排序这两个部分。总的来。
说，就是随机找一个元素（通常是中间的元素），然后把小的放在它的左边，大的放右边，对左右两边的数据继续采用同样的办法。只是为了节省空间，上面采用了左右交换的方法来达到目的。
Analysis：
Implementation：
void QuickSort(int *pData, int left, int right)。
int i, j;
int middle, iTemp;。
i = left;
j = right;
middle = pData[(left + right) / 2]; //求中间值。
do
{
while ((pData[i] < middle) && (i < right)) //从左扫描大于中值的数。
i++;。
while ((pData[j] > middle) && (j > left)) //从右扫描小于中值的数。
j--;。
if (i <= j) //找到了一对值。
{
//交换。
iTemp = pData[i];。
pData[i] = pData[j];。
pData[j] = iTemp;。
i++;。
j--;。
}
} while (i <= j); //如果两边扫描的下标交错，就停止（完成一次）
//当左边部分有值(left<j)，递归左半边。
if(left < j) 。
QuickSort(pData, left, j); 。
//当右边部分有值(right>i)，递归右半边。
if(right > i) 。
QuickSort(pData, i, right); 。
5，希尔Shell：是对Insertion Sort的一种改进，在Insertion Sort中，从第2个位置开始取出数据，每次都是与前一个（step/gap==1）进行比较。Shell Sort修改为，在开始时采用较大的步长step，
从第step位置开始取数据，每次都与它的前step个位置上的数据进行比较（如果有8个数据，初始step==4，那么pos(4)与pos(0)比较，pos(0)与pos(-4)，pos(5)与pos(1)，pos(1)与pos(-3)，
...... pos(7)与pos(3)，pos(3)与pos(-1)），然后逐渐地减小step，直到step==1。step==1时，排序过程与Insertion Sort一样，但因为有前面的排序，这次排序将减少比较和交换的次数。
Shell Sort的时间复杂度与步长step的选择有很大的关系。Shell排序比冒泡排序快5倍，比插入排序大致快2倍。Shell排序比起QuickSort，MergeSort，HeapSort慢很多。但是它相对比较简单，它适合。
于数据量在5000以下并且速度并不是特别重要的场合。它对于数据量较小的数列重复排序是非常好的。
Analysis：
Implementation：
template<typename RandomIter, typename Compare>。
void ShellSort(RandomIter begin, RandomIter end, Compare cmp)。
typedef typename std::iterator_traits<RandomIter>::value_type value_type;。
typedef typename std::iterator_traits<RandomIter>::difference_type diff_t;。
diff_t size = std::distance(begin, end);。
diff_t step = size / 2;。
while (step >= 1)。
{
for (diff_t i = step; i < size; ++i)。
{
value_type key = *(begin+i);。
diff_t ins = i; // current position。
while (ins >= step && cmp(key, *(begin+ins-step)))。
{
*(begin+ins) = *(begin+ins-step);。
ins -= step;。
}
*(begin+ins) = key;。
}
if(step == 2)。
step = 1;。
else
step = static_cast<diff_t>(step / 2.2);。
}
template<typename RandomIter>。
void ShellSort(RandomIter begin, RandomIter end) 。
typedef typename std::iterator_traits<RandomIter>::value_type value_type;。
ShellSort(begin, end, std::less<value_type>());。
6，归并Merge：先将所有数据分割成单个的元素，这个时候单个元素都是有序的，然后前后相邻的两个两两有序地合并，合并后的这两个数据再与后面的两个合并后的数据再次合并，充分前面的过程直到所有的数据都合并到一块。
通常在合并的时候需要分配新的内存。
Analysis：
Implementation：
void Merge(int array[], int low, int mid, int high)。
int k;
int *temp = (int *) malloc((high-low+1) * sizeof(int)); //申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列。
int begin1 = low;。
int end1 = mid;。
int begin2 = mid + 1;。
int end2 = high;。
for (k = 0; begin1 <= end1 && begin2 <= end2; ++k) //比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置。
{
if(array[begin1]<=array[begin2])。
{
temp[k] = array[begin1++];。
}
else
{
temp[k] = array[begin2++];。
}
}
if(begin1 <= end1) //若第一个序列有剩余，直接拷贝出来粘到合并序列尾。
{
memcpy(temp+k, array+begin1, (end1-begin1+1)*sizeof(int));。
}
if(begin2 <= end2) //若第二个序列有剩余，直接拷贝出来粘到合并序列尾。
{
memcpy(temp+k, array+begin2, (end2-begin2+1)*sizeof(int));。
}
memcpy(array+low, temp, (high-low+1)*sizeof(int));//将排序好的序列拷贝回数组中。
free(temp);。
void MergeSort(int array[], unsigned int first, unsigned int last)。
int mid = 0;。
if (first < last)。
{
mid = (first+last)/2;。
MergeSort(array, first, mid);。
MergeSort(array, mid+1,last);。
Merge(array,first,mid,last);。
}
小韩在追星
在各类算法中那种算法排序是最快的？
排序算法 所谓排序，就是使一串记录，按照其中的某个或某些关键字的大小，递增或递减的排列起来的操作。
分类
在计算机科学所使用的排序算法通常被分类为：
计算的复杂度（最差、平均、和最好表现），依据串列（list）的大小（n）。一般而言，好的表现是O。(n log n)，且坏的行为是Ω(n2)。对於一个排序理想的表现是O(n)。仅使用一个抽象关键比较运算的排序算法总平均上总是至少需要Ω(n log n)。
记忆体使用量（以及其他电脑资源的使用）
稳定度：稳定排序算法会依照相等的关键（换言之就是值）维持纪录的相对次序。也就是一个排序算法是稳定的，就是当有两个有相等关键的纪录R和S，且在原本的串列中R出现在S之前，在排序过的串列中R也将会是在S之前。
一般的方法：插入、交换、选择、合并等等。交换排序包含冒泡排序（bubble sort）和快速排序（quicksort）。选择排序包含shaker排序和堆排序（heapsort）。
当相等的元素是无法分辨的，比如像是整数，稳定度并不是一个问题。然而，假设以下的数对将要以他们的第一个数字来排序。
(4, 1) (3, 1) (3, 7) (5, 6)。
在这个状况下，有可能产生两种不同的结果，一个是依照相等的键值维持相对的次序，而另外一个则没有：
(3, 1) (3, 7) (4, 1) (5, 6) (维持次序)。
(3, 7) (3, 1) (4, 1) (5, 6) (次序被改变)。
不稳定排序算法可能会在相等的键值中改变纪录的相对次序，但是稳定排序算法从来不会如此。不稳定排序算法可以被特别地时作为稳定。作这件事情的一个方式是人工扩充键值的比较，如此在其他方面相同键值的两个物件间之比较，就会被决定使用在原先资料次序中的条目，当作一个同分决赛。然而，要记住这种次序通常牵涉到额外的空间负担。
排列算法列表
在这个表格中，n是要被排序的纪录数量以及k是不同键值的数量。
稳定的
冒泡排序（bubble sort） — O(n2) 。
鸡尾酒排序 (Cocktail sort, 双向的冒泡排序) — O(n2) 。
插入排序 （insertion sort）— O(n2) 。
桶排序 （bucket sort）— O(n); 需要 O(k) 额外 记忆体 。
计数排序 (counting sort) — O(n+k); 需要 O(n+k) 额外 记忆体 。
归并排序 （merge sort）— O(n log n); 需要 O(n) 额外记忆体 。
原地归并排序 — O(n2) 。
二叉树排序 （Binary tree sort） — O(n log n); 需要 O(n) 额外记忆体 。
鸽巢排序 (Pigeonhole sort) — O(n+k); 需要 O(k) 额外记忆体 。
基数排序 （radix sort）— O(n·k); 需要 O(n) 额外记忆体 。
Gnome sort — O(n2) 。
Library sort — O(n log n) with high probability, 需要 (1+ε)n 额外记忆体 。
不稳定
选择排序 （selection sort）— O(n2) 。
希尔排序 （shell sort）— O(n log n) 如果使用最佳的现在版本 。
Comb sort — O(n log n) 。
堆排序 （heapsort）— O(n log n) 。
Smoothsort — O(n log n) 。
快速排序 （quicksort）— O(n log n) 期望时间, O(n2) 最坏情况; 对於大的、乱数串列一般相信是最快的已知排序 。
Introsort — O(n log n) 。
Patience sorting — O(n log n + k) 最外情况时间, 需要 额外的 O(n + k) 空间, 也需要找到最长的递增子序列（longest increasing subsequence）
不实用的排序算法
Bogo排序 — O(n × n!) 期望时间, 无穷的最坏情况。
Stupid sort — O(n3); 递回版本需要 O(n2) 额外记忆体 。
Bead sort — O(n) or O(√n), 但需要特别的硬体 。
Pancake sorting — O(n), 但需要特别的硬体 。
排序的算法
排序的算法有很多，对空间的要求及其时间效率也不尽相同。下面列出了一些常见的排序算法。这里面插入排序和冒泡排序又被称作简单排序，他们对空间的要求不高，但是时间效率却不稳定；而后面三种排序相对于简单排序对空间的要求稍高一点，但时间效率却能稳定在很高的水平。基数排序是针对关键字在一个较小范围内的排序算法。
插入排序
冒泡排序
选择排序
快速排序
堆排序
归并排序
基数排序
希尔排序
插入排序
插入排序是这样实现的：
首先新建一个空列表，用于保存已排序的有序数列（我们称之为"有序列表"）。
从原数列中取出一个数，将其插入"有序列表"中，使其仍旧保持有序状态。
重复2号步骤，直至原数列为空。
插入排序的平均时间复杂度为平方级的，效率不高，但是容易实现。它借助了"逐步扩大成果"的思想，使有序列表的长度逐渐增加，直至其长度等于原列表的长度。
冒泡排序
冒泡排序是这样实现的：
首先将所有待排序的数字放入工作列表中。
从列表的第一个数字到倒数第二个数字，逐个检查：若某一位上的数字大于他的下一位，则将它与它的下一位交换。
重复2号步骤，直至再也不能交换。
冒泡排序的平均时间复杂度与插入排序相同，也是平方级的，但也是非常容易实现的算法。
选择排序
选择排序是这样实现的：
设数组内存放了n个待排数字，数组下标从1开始，到n结束。
i=1
从数组的第i个元素开始到第n个元素，寻找最小的元素。
将上一步找到的最小元素和第i位元素交换。
如果i=n－1算法结束，否则回到第3步 。
选择排序的平均时间复杂度也是O(n²)的。
快速排序
现在开始，我们要接触高效排序算法了。实践证明，快速排序是所有排序算法中最高效的一种。它采用了分治的思想：先保证列表的前半部分都小于后半部分，然后分别对前半部分和后半部分排序，这样整个列表就有序了。这是一种先进的思想，也是它高效的原因。因为在排序算法中，算法的高效与否与列表中数字间的比较次数有直接的关系，而"保证列表的前半部分都小于后半部分"就使得前半部分的任何一个数从此以后都不再跟后半部分的数进行比较了，大大减少了数字间不必要的比较。但查找数据得另当别论了。
堆排序
堆排序与前面的算法都不同，它是这样的：
首先新建一个空列表，作用与插入排序中的"有序列表"相同。
找到数列中最大的数字，将其加在"有序列表"的末尾，并将其从原数列中删除。
重复2号步骤，直至原数列为空。
堆排序的平均时间复杂度为nlogn,效率高（因为有堆这种数据结构以及它奇妙的特征，使得"找到数列中最大的数字"这样的操作只需要O(1)的时间复杂度，维护需要logn的时间复杂度），但是实现相对复杂（可以说是这里7种算法中比较难实现的）。
看起来似乎堆排序与插入排序有些相像，但他们其实是本质不同的算法。至少，他们的时间复杂度差了一个数量级，一个是平方级的，一个是对数级的。
平均时间复杂度
插入排序 O(n2)
冒泡排序 O(n2)
选择排序 O(n2)
快速排序 O(n log n) 。
堆排序 O(n log n) 。
归并排序 O(n log n) 。
基数排序 O(n)
希尔排序 O(n1.25)。
冒泡排序
654
比如说这个，我想让它从小到大排序，怎么做呢？
第一步：6跟5比，发现比它大，则交换。564。
第二步：5跟4比，发现比它大，则交换。465。
第三步：6跟5比，发现比它大，则交换。456。