基本思想：两两比较，如果发生逆序则交换，直到所有记录都排好序为止。

常见的交换排序：（1）冒泡排序 （2）快速排序

8.3.1 冒泡排序

基本思想：每趟不断将记录两两比较，并按“前小后大”规则交换。

例：{21，25，49，25'，16，8}

第一趟：{21，25，25'，16，8，49}

第二趟：{21，25，16，8，25'，49}

第三趟：{21，16，8，25，25'，49}

第四趟：{16，8，21，25，25'，49}

第五趟：{8，16，21，25，25'，49}

冒泡排序算法：

void Bubble_Sort(SQList *L)
{RedType x; //交换时临时存储for (int i = 1; i < L->length; i++)for (int j = 1; j <= L->length - i; j++){if (L->r[j].key > L->r[j+1].key){x = L->r[j];L->r[j] = L->r[j+1];L->r[j+1] = x;}}
}

改进后的冒泡排序：

void Bubble_Sort(SQList *L)
{int flag = 1;RedType x;for (int i = 1; i < L->length; i++){flag = 0;for (int j = 1; j <= L->length-i; j++){if (L->r[j].key > L->r[j+1].key){flag = 1;x = L->r[j];L->r[j] = L->r[j+1];L->r[j+1] = x;}}}
}

8.3.2 快速排序

基本思想：

（1）任取一个元素（如：第一个）为中心；

（2）所有比它小的元素一律前放，比它大的元素一律后放，形成左右两个子表；

（3）对各子表重新选择中心元素，并依此规律调整，直到每个子表的元素只剩一个。

通过一趟排序，将待排序记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，则可分别对这两部分进行排序，以达到整个序列有序。

具体实现：选定一个中间数作为参考，所有元素与之相比，小的调到其左边，大的调到其右边。

中间数：可以是第一个元素、最后一个元素、最中间的一个元素、任选一个元素等。

例如：

 这一趟之后就形成了两个子表，再以相同的方法继续对左右子表排序。

快速排序算法：

void Quick_Sort(QSList *L, int low, int high)
{if (low < high){int pivotloc = Partition(L, low, high);Quick_Sort(L, low, pivotloc-1);Quick_Sort(L, pivotloc+1, high);}
}int Partition(SQList *L, int low, int high)
{L->r[0] = L->r[low];KeyType pivotkey = L->r[low].key;while (low < high){while (low < high && L->r[high].key >= pivotkey)high--;L->[low] = L->r[high];while (low < high && L->r[low] <= pivotkey)low++;L->r[high] = L->r[low];} L->r[low] = L->r[0];return low;
}