首页 / 操作系统 / Linux / 冒泡排序

思想

实现

改进

设比较标志法

• 思想
  普通的冒泡排序，即使原数列已经有序，仍然会进行N - 1趟排序。可以加入一标志性变量，用于标志某一趟排序过程中是否有数据交换。如果进行某一趟排序时并没有进行数据交换，则说明数据已经按要求排列好，可立即结束排序，避免不必要的比较过程。如对序列3 1 4 5 6进行排序时，只进行2趟算法就结束了（第二趟没有发生交换使得排序提前结束）。注意，当输入序列是逆序的，该算法和传统冒泡排序进行了一样多次比较。
• 算法实现void FlagedBubbleSort（int a[], int n）{int i, j, swaped;for（i = 0; i < n - 1; ++i）{swaped = 0;for（j = 0; j < n - 1 - i; ++j）if（a[j] > a[j + 1]）{swaped = 1;Swap（a + j, a + j + 1）;}if（！swaped）break;}}

剔除法

• 思想
  假设某一位置pos后的元素都已排序，而pos前的元素未排序完，那么上述算法仍然会扫描pos位置后的元素。因此，可设置一标志性变量pos，用于记录每趟排序中最后一次进行交换的位置。由于pos位置后的元素均已排序完，故在进行下一趟排序时只要扫描到pos位置即可。可形象地认为pos位置后的n-pos+1个元素都被从待排序列中剔除了。
• 算法实现void RejectBubbleSort（int a[], int n）{int i, high, rpos;high = n - 1;while（high > 0）{rpos = 0;for（i = 0; i < high; ++i）if（a[i] > a[i + 1]）{rpos = i; //记录交换位置Swap（a + i, a + i + 1）;}high = rpos; //下一趟应该扫描到达的位置}}

双向剔除法

• 思想
  上面的剔除法只能处理某一方向上的已排序子序列，使用双向的扫描可进一步优化冒泡排序。
• 算法实现void DoubleBubbleSort（int a[], int n）{int i, j;int low = 0, high = n - 1;int lpos, rpos;while（low < high）{rpos = low;for（i = low; i < high; ++i） //正向冒泡if（a[i] > a[i + 1]）{Swap（a + i, a + i + 1）;rpos = i;}high = rpos;lpos = high;for（j = high; j > low; --j） //反向冒泡if（a[j] < a[j - 1]）{Swap（a + j, a + j - 1）;lpos = j;}low = lpos;}}