一、程式描述
冒泡排序(BubbleSort)簡單來講就是通過對其中的元素按順序兩兩進行對比，按照規則不斷交換，使得一些元素慢慢被換到后面，就像是水中的氣泡慢慢的浮出水面（跑到后面）一樣，這是一種簡單的基于比較大小的排序演算法，冒泡排序利用了不等式傳遞的思想，
演算法原理：如果想把某個陣列按照遞增順序排列，那么應該從頭開始比較相鄰的兩個元素，如果后面一個元素比前面一個要大，說明順序不對，就把他們換個位置，直到所有元素全部交換完成，則排序完成，冒泡排序一般用于初學計算機程式設計的人理解演算法，
演算法穩定性：如果相等的兩個元素相鄰，那么根據演算法定義不會發生交換，如果相等的兩個元素不相鄰，那么通過其他的兩兩交換讓他們相鄰后也不會發生交換，所以相同元素的順序不會發生改變，冒泡排序是一種穩定排序演算法，
演算法優化：
1、冒泡的同時把“水”沉下去，（上浮+下沉）
2、泡泡到頂以后再也不進行掃描，（減少無效掃描）
3、如果檢測到一整輪沒有發生交換，直接結束排序，
二、程式要點
1、冒泡的同時把“水”沉下去，（上浮+下沉）雙向排序
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
void bubble_sort_down(int arr[], int sz)//冒泡排序，雙向掃描
{
int i = 0;
int t;
int m;
for (i = 0; i < (sz)/2; i++)//進行元素個數減一次排序,雙向排序中可以讓排序次數減半
{
int flag = 1;//定義一個整型變數一會用來判斷if陳述句
int j;
int k;
for (j = 0; j < sz - 1 - i; j++)//每次排序次數比較次數減少i個，也就是不再對已經上浮到位的元素進行比較
{
if (arr[j] > arr[j + 1])
{
t = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = t;
flag = 0;//程式如果沒來這，說明這一次掃描沒有發生過換位，所以可以直接結束排序
}
}
for (k = sz -1-i; k > 0; k--)//從小到大排
{
if (arr[k] < arr[k - 1])
{
m = arr[k];
arr[k] = arr[k - 1];
arr[k - 1] = m;
flag = 0;
}
}
if (flag == 1)
{
break;
}
}
}
int main()
{
int i = 0;
int arr[10] = { 9,8,7,6,5,4,3,2,1,0 };//排為升序
int sz = sizeof(arr) / sizeof(arr[0]);
bubble_sort_down(arr, sz);//冒泡排序函式
for (i = 0; i < sz; i++)
{
printf("%d\n", arr[i]);
}
return 0;
}
2、泡泡到頂以后再也不對它進行掃描，函式呼叫
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
void bubble_sort(int arr[],int sz)//冒泡排序，這個代碼效率比較低
{
int i = 0;
int t;
for (i = 0; i < sz-1; i++)//進行元素個數減一次排序
{
int j;
for (j = 0; j <sz-1-i; j++)//每次排序次數比較次數減少i個，也就是不再對已經上浮到位的元素進行比較
{
if (arr[j] > arr[j + 1])
{
t = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = t;
}
else
continue;
}
}
}
int main()
{
int i=0;
int arr[10] = { 9,8,7,6,5,4,3,2,1,0 };//排為升序
int sz = sizeof(arr) / sizeof(arr[0]);
bubble_sort(arr,sz);//冒泡排序函式
for (i = 0; i < sz; i++)
{
printf("%d\n", arr[i]);
}
return 0;
}
3、如果檢測到一整輪沒有發生交換，直接結束排序，
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
void bubble_sort(int arr[],int sz)//冒泡排序，一定的改進
{
int i = 0;
int t;
for (i = 0; i < sz-1; i++)//進行元素個數減一次排序
{
int flag = 1;//定義一個整型變數一會用來判斷if陳述句
int j;
for (j = 0; j <sz-1-i; j++)//每次排序次數比較次數減少i個，也就是不再對已經上浮到位的元素進行比較
{
if (arr[j] > arr[j + 1])
{
t = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = t;
flag = 0;//程式如果沒來這，說明這一次掃描沒有發生過換位，所以可以直接結束排序
}
else
continue;
}
if (flag == 1)
{
break;
}
}
}
int main()
{
int i=0;
int arr[10] = { 9,8,7,6,5,4,3,2,1,0 };//排為升序
int sz = sizeof(arr) / sizeof(arr[0]);
bubble_sort(arr,sz);//冒泡排序函式
for (i = 0; i < sz; i++)
{
printf("%d\n", arr[i]);
}
return 0;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/237638.html
標籤：其他