考虑到各种排序方法的复杂运算有时候难以理解,以致于带来的记忆困难,将其转化为更方便自己理解的思路方式,并作出以下的记录。
冒泡排序:
把数组中的数依次将相邻的两个数进行对比,把较大的数排列在右边,最后把最大的数排在了数组最右边,完成第一轮对比;忽略最大的数进行第二轮相同的对比步骤,把第二大的数排在倒数第二位,如此类推,最多经过(数组总长度-1)次排序,完成整个数组的从小到大排列。
选择排序:
指定一个位置(通常是最左或最右),依次将数组中的数两两进行对比,把其中较小(或较大)的数进行标记,再将被标记的数与下一个数进行对比,直到对比出整个数组中最小(或最大)的数后,将其放到指定的位置,完成第一个数的排序;将数组中剩下的数重复进行相同的对比方法,找出第二个最小(或最大)的数,将其放到第一个指定位置的后面,以此类推,直到最后完成整个数组的从小到大(或从大到小)的排序。
插入排序:
对比数组中的前两个数,将较大的数排列在右边;加入第三个数与前面两个数进行对比,当第三个数遇到比自身大的数时,移动到较大数的左边,直到遇到比自己小的数时停止移动并插入到其中或直到移动到最左边为止(即自身为三个对比数中最小的数)。加入第四个数,以同样的方法进行对比插入,直到完成整个数组的移动插入,即可完成整个数组的从小到大排序。(从大到到的排序方法类同)
归并排序:
这个算法有点抽象。将整个数组拆分成两部分,再将拆分好两个部分分别再拆开成四、八、十六....一直拆到最小的对比单位:每部分只剩下两个对比数为止(如果是奇数位数组时最后一组只有一个数);(假设最小单位组为n,包含最少的两个数或一个数,往上一级包含两组共4个数的则为2n单位组,以此类推4n、8n...)开始进行对比,将每个n组自身的两个数进行对比,并将其中较大的数放置该组的右边;往上一级,将2n组的两组n的数进行对比,第一组第一个数与第二组的第一个数进行对比,较小的数排列在新的2n组序列的第一位;剩下的较大数与之前较小数所在组的下一个数进行对比,其中较小的排列在新的2n组的第二位,以此类推完成每个2n组的从小到大排序;继续往上,完成4n、8n......单位组的排序,一直到完成整个数组的从小到大排序。(从大到小的方法类同)
快速排序:
这是一种“自私”排序法,选定数组的第一个数为基数,与整个数组的其他数进行对比,将所有比这个基数小的数(假设为组n)移动到其左边,于是第一个基数在整个数组中的正确排序就完成了;选择n中的第一个数作为第二个基数与n剩下的其他数进行对比,所有比这个数小的(假设为2n)都移到到其左边,第二个基数在数组整体中的位置排序完成;以此类推将2n中的第一个数作为第三个基数与2n中其他数进行对比,比基数小的都移动到其左边....完成所有基数的左边数(即比基数小的数)的排序后,倒回来开始从最后一个基数对比基数的右边数(即比基数大的数),以相同的方法完成所有右边数的排序;最终完成整个数组的从小到大排序。
随机化快速排序:
随机化快速排序与快速排序基本一致,其中的区别在于:在选择下一个基数时,并不以n组的第一个数作为第二个基数,而是在整个数组中随机选择一个作为第二个基数进行对比,这种做法可以避免了在快速排序中,每次都选中仅比上一个基数大一点的数作为第二个基数,导致整体对比排序的次数过多,最多的对比次数即出现了快速排序中最慢最差的排序效率。随机化快速排序并不一定每次都是最快的,但却避免了最慢效率的情况出现。
限于自身的理解程度,可能描述总结得不够清晰,只能在之后加深理解后更改或补充。