交换排序的基本思想是：通过“交换”无序序列中的记录从而得到其中关键字最小或最大的记录，并将它加入到有序序列（开始时为空）中，从而增加记录的有序序列的长度。本节介绍两种交换排序：冒泡排序（bubble sort）和快速排序（quick sort）。

1.冒泡排序

冒泡排序是一种简单的交换类排序方法。它是通过相邻的数据元素的交换，逐步将待排序序列变成有序序列的过程。冒泡排序的基本思想是：从头扫描待排序记录序列，在扫描的过程中依次比较相邻的两个元素的大小。以升序为例：在第一趟排序中，对n个记录进行如下操作：若相邻的两个记录的关键字比较，逆序时就交换位置。在扫描的过程中，不断地将相邻两个记录中关键字大的记录向后移动，最后将待排序记录序列中的最大关键字记录交换到了待排序记录序列的末尾，这也是最大关键字记录排序完应该存储的位置。然后进行第二趟冒泡排序，对前n-1个记录进行同样的操作，其结果是使次大的记录被放在第n-1个记录的位置上。

【效率分析】对于冒泡排序：

冒泡排序的空间效率：仅用了一个辅助单元。 

时间效率：总共要进行n-1趟冒泡，对j个记录的表进行一趟冒泡需要j-1次关键码比较。

冒泡排序的时间复杂度为O(n*n)。

冒泡排序是稳定的排序方法。

2.快速排序

就排序时间而言，快速排序法是目前内部排序中速度较快的方法，被认为是一种最好的内部排序方法，故称快速排序。在冒泡排序中，由于扫描过程中只对相邻的两个记录进行比较，因此在互换两个相邻记录时只能消除一个逆序。如果能通过两个(不相邻的) 记录的交换，消除待排序记录中的多个逆序，则会大大加快排序的速度。快速排序方法就是想通过一次交换而消除多个逆序。

快速排序的基本思想是：通过比较关键字、交换记录，以某个记录为界(通常选取第一个记录，称为支点)，将待排序列分成两部分。其中，一部分所有记录的关键字大于等于支点记录的关键字，另一部分所有记录的关键字小于支点记录的关键字。将待排序列按关键字以支点记录分成两部分的过程，称为一次划分。对各部分不断划分，直到整个序列按关键字有序。