交换排序

交换排序的基本思想：两两比较待排序的关键字，发现两个元素的次序相反时即进行交换，直到没有反序的元素为止。

一、冒泡排序

1.排序思路

冒泡排序也称气泡排序，是一种典型的交换排序方法，其基本思想是：通过无序区中相邻元素间关键字的比较和位置的交换，使关键字最小的元素如气泡一般逐渐往上“漂浮”直至“水面”。

2.排序算法

3.算法分析

冒泡排序的时间复杂度为O(n).最坏时间复杂度为O（n*n）

二、快速排序

1.排序思路

快速排序是由冒泡排序改进而得的，它的基本思想是：在待排序的n个元素中任取一个元素，（通常取第一个元素）作为基准，把该元素放入适当位置后，数据序列被此元素划分成两部分，所有关键字比该元素关键字小的元素放置在前一部分，所有关键字比他大的元素放置在后一部分，并把该元素排在这两部分的中间（称该元素归位），这个过程称做一趟快速排序，之后对所有划分出来的两部分分别重复上述过程，直至每部分内只有一个元素或为空为止。简而言之，每趟将表的第一个元素放入适当位置，将表一分为二，对子表按递归方式继续这种划分，直至划分的子表长为1或0。

说明：快速排序每趟仅将一个元素归位。

2。排序算法

3.算法分析

时间复杂度：

最好情况：O(n log2n)

最坏情况：O(n*n)