排序那回事

现将排序算法总结如下：

一、直接插入排序
思想：将数组分为有序区和无序区，通过将无序区元素依次按大小顺序加入到有序区，直到有序区中容纳了所有的元素，则排序完成。

二、希尔排序（又称缩小增量排序，是对直接插入排序的一种改进算法）
思想：1、首先将待排序数据进行分组，每组中的数据是由数组中间距为某个具体数值或该具体数值倍数的元素，例如：一个数组a[10]，间距选择5，则其中的一组为a[0]、a[5]，还有一组为a[1]、a[6]，一组为a[2]、a[7]，一组为a[3]、a[8]，一组为a[4]、a[9]，这里每组中的元素数组中的位置都间隔为5。
         2、对每组中的数据都进行直接插入排序。
         3、然后对数组进行继续分组，此时组中的元素依然来自于数组中间距为某一具体数值或该具体数值倍数的元素，只是这里的间距应该小于步骤1中的间距。
         4、对步骤3得出来的每一组进行直接插入排序。
         5、重复3、4，直至元素的间距为1。

这里介绍一种选间距的办法，即第一次选择数组元素个数的一半作为间距，第二次选择第一次间距值的一半，第三次选择第二次间距值的一半，依次类推...直至间距值为1停止排序，数组中的值已经按序排列。

三、冒泡排序（假设要求从大到小排好序）
思想：1、第1趟从数组第一个元素开始到数组最后一个元素为止，依次两两比较数组中的元素，每次比较将较小的元素放在这两个元素所在位置靠后的位置，从而这一次排序得到一个最小数放在数组最后。
         2、第二趟从数组第一个元素开始到数组倒数第二个元素为止，依次两两比较数组中的元素，每次比较将较小数放在较后面的位置，从而该趟排序得到次小数。
         3、第i趟从数组第一个元素开始到数组倒数第第i个元素为止，依次两两比较数组中的元素，每次比较将较小数放在较后面的位置。到第n-1趟排序数组必将排好序，此处的n是数组中元素的个数。

注意：提一个小小的建议，可以将冒泡排序算法的性能提高一点点，就是：设置一个标志变量，用来标志各趟排序，元素是否真的被重新排过序，如果某一趟排序该标志变量表明未进行过排序，则说明数组已经排好序，我们则可以提前终止排序，而不用排n-1趟。

四、快速排序（假设要求从大到小排序）
思想：1、选择数组中的一个元素作为基准元素，所有比它小的元素放在它的后面，所有比它大的元素放在它的前面。
         2、完成步骤1后，数组被步骤1中的基准元素分为两半，对这两半元素分别应用步骤1中的思路。然后每一半的数组元素又分别被它们所选取的基准元素分成两半，将得到的四组元素分别应用步骤1的思想，依次类推，直至每个组中的元素只有一个完成排序。

五、直接选择排序（假设要求数组从小到大排序）
思想：1、第一趟找到最小元素所在的位置，将它和数组的第一个元素交换位置。
         2、第i 趟找到倒数第i 小的元素，和数组的第i 个元素交换位置，直至第n-1趟，其中n表示数组中的元素个数。

六、堆排序
思想：1、利用大根堆或小根堆思想建立堆，此处以大根堆为例；然后通过依次取出大根堆的跟部元素，然后将数组最后一个元素放在该根部元素所在的位置（即数组的第一个位置）。
         2、将数组重新排列顺序，使其符合大根堆的思想，取出大根堆的跟部元素。
         3、重复步骤2，直至数组堆中只有一个元素位置。得到一个从小到大的数组。

七、归并排序
思想：将数组分为若干有序序列组，然后对这些有序序列进行合并，将其合并成比之前有序序列组个数少的有序序列，直至变成一个有序序列，排序结束。

八、基数排序
思想：将数字按位数划分出n个关键字，每次针对一个关键字进行排序，然后针对排序后的序列进行下一个关键字的排序，循环至所有关键字都使用过则排序完成。

九、桶排序
思想：将待排序数据按照规定分为若干组，每个组内分别进行用桶排序算法或者别的排序算法进行排序，然后完成排序。