文章目錄
- 三大基礎排序演算法(冒泡,選擇,插入)
- 一.冒泡排序法
- 原理決議:
- 代碼實作:
- 注意:
- 二.選擇排序法
- 原理決議:
- 代碼實作:
- 注意:
- 三.插入排序法
- 原理決議:
- 代碼實作:
三大基礎排序演算法(冒泡,選擇,插入)
一.冒泡排序法
原理決議:
時間復雜度: O(n2)
- 比較相鄰的元素，如果第一個比第二個大，就交換他們兩個，
- 對每一對相鄰元素做同樣的作業，從開始第一對到結尾的最后一對，在這一點，最后的元素應該會是最大的數，
- 針對所有的元素重復以上的步驟，除了最后一個，
- 持續每次對越來越少的元素重復上面的步驟，直到沒有任何一對數字需要比較，
代碼實作:
通過兩層回圈全套實作
外層回圈:冒泡趟數
內層回圈:冒泡次數
注意:
1 每多排好一個資料,可以將內層回圈次數減少一次,從而提高效率.
2 總共只需要為n - 1個資料排序,剩下的一個是最小值,不需要再排序
int main() {
// 定義一個未序一維陣列
int arr[10] = { 1,3,6,9,5,8,-1,2,5,7 };
// 冒泡排序
// 外層回圈: 控制比較的"趟數",每一趟排好一個資料
for (int i = 9; i > 0; i--)
{
// 內層回圈: 控制比較的"次數"
// 次數受外層回圈控制 每趟少比較一次
for (int j = 0; j < i; j++) {
// 比較大小
// 當前資料比后一個大
if (arr[j] > arr[j + 1]) {
// 交換
arr[j] = arr[j] ^ arr[j + 1];
arr[j + 1] = arr[j] ^ arr[j + 1];
arr[j] = arr[j] ^ arr[j + 1];
}
}
}
// 輸出
for (size_t i = 0; i < 10; i++)
{
printf("%d ",arr[i]);
}
return 0;
}
二.選擇排序法
原理決議:
時間復雜度: O(n^2)
首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再從剩余未排序元素中繼續尋找最小（大）元素，然后放到已排序序列的末尾，以此類推，直到所有元素均排序完畢，
代碼實作:
兩層回圈嵌套,內層回圈尋找最大值的下標
注意:
- 選擇最大值的時候假定第一個資料是最大的 碰到比他大的就更新下標
- 每次回圈之前 最大值的下標要重置
#include<stdio.h>
int main() {
// 定義一個未序一維陣列
int arr[10] = { 1,3,6,9,5,8,-1,2,5,7 };
// 選擇排序
int maxIndex = 0;
int temp;
for (int i = 9; i > 0; i--)
{
maxIndex = 0;
for (int j = 0; j <= i; j++) {
if (arr[maxIndex] < arr[j]) {
maxIndex = j;
}
}
if (maxIndex != i) {
temp = arr[maxIndex];
arr[maxIndex] = arr[i];
arr[i] = temp;
}
}
// 輸出
for (size_t i = 0; i < 10; i++)
{
printf("%d ",arr[i]);
}
return 0;
}
三.插入排序法
原理決議:
時間復雜度: O(N^(1-2))
將元素插入到一個已序陣列中相應的位置
沒有排序的陣列,無論是升序還降序,最前面的元素(單個元素)都可以視為已序
代碼實作:
將最前面的元素視為已序陣列,按照排序規則選擇位置插入.
兩層回圈嵌套.
外層回圈: 資料個數
內層回圈: 控制比較的次數
#include<stdio.h>
int main() {
// 定義一個未序一維陣列
int arr[10] = { 1,3,6,9,5,8,-1,2,5,7 };
// 插入排序
for (int i = 1; i < 10; i++) // 進行9次排序(第0個元素當做已序)
{
// 內層回圈: arr[i]從arr[1]開始比較
for (int j = i - 1; j >= 0; j--) {
// 比較
if (arr[j + 1] < arr[j]) {
// 如果后面的值小于(升序)/大于(降序)前面的值則交換
arr[j + 1] = arr[j + 1] ^ arr[j];
arr[j] = arr[j + 1] ^ arr[j];
arr[j + 1] = arr[j + 1] ^ arr[j];
}
else break; // 減少多余的判斷
}
}
// 輸出
for (size_t i = 0; i < 10; i++)
{
printf("%d ",arr[i]);
}
return 0;
}
r[j + 1] ^ arr[j];
}
else break; // 減少多余的判斷
}
}
// 輸出
for (size_t i = 0; i < 10; i++)
{
printf("%d ",arr[i]);
}
return 0;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/263721.html
標籤：其他