冒泡排序
冒泡排序
思想
重复地走访要排序的数列,一次比较两个元素,如果它们的顺序不符合要求就交换它们的位置。N个数需要N - 1趟排序,每一趟排序使得最大数冒出(升序)或最小数冒出(降序)。
实现
/**
* @brief 交换两指针指向的对象的值
*/
void Swap(int *a, int *b);
传统冒泡排序的C语言实现如下:
//升序方式
void BubbleSort(int a[], int n)
{
int i, j;
for(i = 0; i < n - 1; ++i)
for(j = 0; j < n - 1 - i; ++j)
if(a[j] > a[j + 1])
Swap(a + j, a + j + 1);
}
改进
设比较标志法
-
思想
普通的冒泡排序,即使原数列已经有序,仍然会进行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; } }
本文永久更新链接地址:
评论暂时关闭