##Basics Sorting - 基础排序算法 算法复习——排序

###算法分析

1. 时间复杂度-执行时间(比较和交换次数)
2. 空间复杂度-所消耗的额外内存空间

• 使用小堆栈或表
• 使用链表或指针、数组索引来代表数据
• 排序数据的副本

对具有重键的数据(同一组数按不同键多次排序)进行排序时，需要考虑排序方法的稳定性，在非稳定性排序算法中需要稳定性时可考虑加入小索引。

稳定性：如果排序后文件中拥有相同键的项的相对位置不变，这种排序方式是稳定的。

常见的排序算法根据是否需要比较可以分为如下几类：

• Comparison Sorting
  1.Bubble Sort
  2.Selection Sort
  3.Insertion Sort
  4.Shell Sort
  5.Merge Sort
  6.Quck Sort
  7.Heap Sort
• Bucket Sort
• Counting Sort
• Radix Sort

从稳定性角度考虑可分为如下两类： -稳定 -非稳定

有关排序法的文章

• - 各类排序算法的「平均、最好、最坏时间复杂度」总结。
• - 基于 Python 的较为清晰的总结。
• - 总结了一些常用常问的排序算法。

##Bubble Sort - 冒泡排序 核心：冒泡，持续比较相邻元素，大的挪到后面，因此大的会逐步往后挪，故称之为冒泡。

示例

#!/usr/bin/env pythondef bubbleSort(alist):    for i in xrange(len(alist)):        print(alist)        for j in xrange(1, len(alist) - i):            if alist[j - 1] > alist[j]:                alist[j - 1], alist[j] = alist[j], alist[j - 1]    return alistunsorted_list = [6, 5, 3, 1, 8, 7, 2, 4]print(bubbleSort(unsorted_list))

php冒泡：

     $alist[$j])   {       $tmp = $alist[$j - 1];       $alist[$j -1] = $alist[$j] ;       $alist[$j] = $tmp;   }  }}return $alist;} $unsorted_list = array(6, 5, 3, 1, 8, 7, 2, 4); print_r(bubbleSort($unsorted_list));

复杂度分析

平均情况与最坏情况均为 $$O(n^2)$$, 使用了 temp 作为临时交换变量，空间复杂度为 $$O(1)$$.