C語(yǔ)言實(shí)現(xiàn)選擇排序、直接插入排序、冒泡排序的示例

來(lái)源：本站原創(chuàng)|時(shí)間：2020-01-10|欄目：C語(yǔ)言|點(diǎn)擊：次

選擇排序
選擇排序是一種簡(jiǎn)單直觀的排序算法，其核心思想是：遍歷數(shù)組，從未排序的序列中找到最小元素，將其放到已排序序列的末尾。

時(shí)間復(fù)雜度：O(n^2)

穩(wěn)定性：不穩(wěn)定

 /*
 * @brief  selection sort
 */
 void
 selection_sort(int a[], int n)
 {
   int i, j, min, tmp;
   
   for (i = 0; i < n - 1; ++i) {
     min = i;
     for (j = i+1; j < n; ++j) {
       if (a[j] < a[min]) {
         min = j;
       }
     }
     if (min != i) {
       tmp = a[min];
       a[min] = a[i];
       a[i] = tmp;  
     }        
   }
 }

直接插入排序
直接插入排序是一種比較容易理解的排序算法，其核心思想是遍歷數(shù)組，將數(shù)組中的元素逐個(gè)插入到已排序序列中。

時(shí)間復(fù)雜度：O(n^2)

穩(wěn)定性：穩(wěn)定

實(shí)現(xiàn)：

 /* @brief insetion sort
 * insert the new element to the sorted subarray
 */
 void
 insertion_sort(int a[], int n)
 {
   int i, j, num;
 
   for (i = 1; i < n; ++i) {
     num = a[i];
     for (j = i - 1; j >= 0 && a[j] > num; --j)
       a[j+1] = a[j];
     a[j+1] = num;
   }
 }

冒泡排序
冒泡排序是最基本的排序算法之一，其核心思想是從后向前遍歷數(shù)組，比較a[i]和a[i-1]，如果a[i]比a[i-1]小，則將兩者交換。這樣一次遍歷之后，最小的元素位于數(shù)組最前，再對(duì)除最小元素外的子數(shù)組進(jìn)行遍歷。進(jìn)行n次（n數(shù)組元素個(gè)數(shù)）遍歷后即排好序。外層循環(huán)為n次，內(nèi)層循環(huán)分別為n-1， n-2…1次。

時(shí)間復(fù)雜度： O(n^2)

穩(wěn)定性：穩(wěn)定

實(shí)現(xiàn)：

 /* @brief  bubble sort
 * move the smallest element to the front in every single loop
 */
 void
 bubble_sort(int a[], int n)
 {
   int i, j, tmp;
 
   for (i = 0; i < n; ++i) {
     for (j = n - 1; j > i; --j) {
       if (a[j] < a[j-1]) {
         tmp = a[j];
         a[j] = a[j-1];
         a[j-1] = tmp;
       }
     }
   }
 }

上一篇：Windows系統(tǒng)下使用C語(yǔ)言編寫(xiě)單線程的文件備份程序

欄目：C語(yǔ)言

下一篇：在C語(yǔ)言編程中使用變量的基礎(chǔ)教程

本文標(biāo)題：C語(yǔ)言實(shí)現(xiàn)選擇排序、直接插入排序、冒泡排序的示例

本文地址：http://www.jygsgssxh.com/a1/Cyuyan/2486.html

更多C語(yǔ)言