C語言實(shí)現(xiàn)九大排序算法的實(shí)例代碼

更新時(shí)間：2021年01月15日 12:00:23 作者：畏新

這篇文章主要給大家介紹了關(guān)于C語言實(shí)現(xiàn)九大排序算法的相關(guān)資料，文中通過示例代碼介紹的非常詳細(xì)，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧

直接插入排序

將數(shù)組分為兩個(gè)部分，一個(gè)是有序部分，一個(gè)是無序部分。從無序部分中依次取出元素插入到有序部分中。過程就是遍歷有序部分，實(shí)現(xiàn)起來比較簡單。

#include <stdio.h>

void insertion_sort(int arr[], int array_length) {
 for (int i = 0; i < array_length; ++i) {
  int data = arr[i];
  int j = 0;
  while (arr[j] < arr[i]) {
   j++;
  }
  for (int k = i; k >= j + 1; k--) {
   arr[k] = arr[k - 1];
  }
  arr[j] = data;
 }
}

void print_array(int arr[], int array_length) {
 for (int i = 0; i < array_length; ++i) {
  printf("%d ", arr[i]);
 }
 printf("\n");
}

int main() {
 int arr[7] = {8, 2, 6, 0, 5, 7, 4};
 insertion_sort(arr, 7);
 print_array(arr, 7);
 return 0;
}

折半插入排序

折半插入再直接插入上有改進(jìn)，用折半搜索替換遍歷數(shù)組，在數(shù)組長度大時(shí)能夠提升查找性能。其本質(zhì)還是從無序部分取出元素插入到有序部分中。

#include <stdio.h>

void binary_insertion_sort(int arr[], int array_length) {
 int i, j, low = 0, high = 0, mid;
 int temp = 0;
 for (i = 1; i < array_length; i++) {
  low = 0;
  high = i - 1;
  temp = arr[i];
  while (low <= high) {
   mid = (low + high) / 2;
   if (arr[mid] > temp) {
    high = mid - 1;
   } else {
    low = mid + 1;
   }
  }
  for (j = i; j > low; j--) {
   arr[j] = arr[j - 1];
  }
  arr[low] = temp;
 }
}

void print_array(int arr[], int array_length) {
 for (int i = 0; i < array_length; ++i) {
  printf("%d ", arr[i]);
 }
 printf("\n");
}

int main() {
 int brr[5] = {2, 6, 0, 5, 7};
 binary_insertion_sort(brr, 5);
 print_array(brr, 5);
 return 0;
}

希爾排序

希爾排序的核心就是根據(jù)步長分組，組內(nèi)進(jìn)行插入排序。關(guān)于步長的選取，第一次步長取元素的個(gè)數(shù)，后面每次取原來步長的一半。

希爾排序?qū)儆诓迦肱判虻囊环N。

#include <stdio.h>

void shell_sort(int arr[], int array_length) {
 int step = array_length / 2;
 while (step >= 1) {
  for (int i = 0; i < array_length; i += step) {
   int data = arr[i];
   int j = 0;
   while (arr[j] < arr[i]) {
    j++;
   }
   for (int k = i; k >= j + 1; k--) {
    arr[k] = arr[k - 1];
   }
   arr[j] = data;
  }
  step = step / 2;
 }
}

void print_array(int arr[], int array_length) {
 for (int i = 0; i < array_length; ++i) {
  printf("%d ", arr[i]);
 }
 printf("\n");
}

int main() {
 int crr[10] = {73, 22, 93, 43, 55, 14, 28, 65, 39, 81};
 shell_sort(crr, 10);
 print_array(crr, 10);
 return 0;
}

冒泡排序

冒泡的特點(diǎn)是兩兩交換。通過交換把最大的元素交換到后面去了，每次循環(huán)遍歷都把無序部分最大的“沉”到后面去。小數(shù)上“浮”和大數(shù)下“沉”其實(shí)沒有差別，都能實(shí)現(xiàn)冒泡。

#include <stdio.h>

void bubble_sort(int arr[], int array_length) {
 for (int i = 0; i < array_length - 1; ++i) {
  for (int j = 0; j < array_length - i - 1; ++j) {
   if (arr[j] > arr[j + 1]) {
    int temp = arr[j];
    arr[j] = arr[j + 1];
    arr[j + 1] = temp;
   }
  }
 }
}

void print_array(int arr[], int array_length) {
 for (int i = 0; i < array_length; ++i) {
  printf("%d ", arr[i]);
 }
 printf("\n");
}

int main() {
 int drr[7] = {8, 2, 6, 0, 5, 7, 4};
 bubble_sort(drr, 7);
 print_array(drr, 7);
 return 0;
}

快速排序

快排的精髓在于選定一個(gè)標(biāo)準(zhǔn)（通常選數(shù)組的第一個(gè)元素），然后將所有元素根據(jù)標(biāo)準(zhǔn)分為小于和大于兩個(gè)部分，然后這兩個(gè)部分再選取標(biāo)準(zhǔn)，繼續(xù)遞歸下去，不難想象最終排序結(jié)果是整體有序的。

#include <stdio.h>

int getStandard(int arr[], int low, int high) {
 int flag = arr[low];
 while (low < high) {
  while (low < high && arr[high] >= flag) {
   high--;
  }
  if (low < high) {
   arr[low] = arr[high];
  }
  while (low < high && arr[low] <= flag) {
   low++;
  }
  if (low < high) {
   arr[high] = arr[low];
  }
 }
 arr[low] = flag;
 return low;
}

void quick_sort(int arr[], int low, int high) {
 if (low < high) {
  int pos = getStandard(arr, low, high);
  quick_sort(arr, low, pos - 1);
  quick_sort(arr, pos + 1, high);
 }
}

void print_array(int arr[], int array_length) {
 for (int i = 0; i < array_length; ++i) {
  printf("%d ", arr[i]);
 }
 printf("\n");
}

int main() {
 int err[10] = {73, 22, 93, 43, 55, 14, 28, 65, 39, 81};
 quick_sort(err, 0, 9);
 print_array(err, 10);
 return 0;
}

直接選擇排序

如其名，直接選擇一個(gè)最小的放到最前面，但是遍歷往往導(dǎo)致效率較低。

#include <stdio.h>

void select_sort(int arr[], int array_length) {
 for (int i = 0; i < array_length; ++i) {
  int min_pos = i;
  for (int j = i; j < array_length; ++j) {
   if (arr[min_pos] > arr[j])
    min_pos = j;
  }
  int temp = arr[min_pos];
  arr[min_pos] = arr[i];
  arr[i] = temp;
 }
}

void print_array(int arr[], int array_length) {
 for (int i = 0; i < array_length; ++i) {
  printf("%d ", arr[i]);
 }
 printf("\n");
}

int main() {
 int frr[7] = {8, 2, 6, 0, 5, 7, 4};
 select_sort(frr, 7);
 print_array(frr, 7);
 return 0;
}

堆排序

將數(shù)組轉(zhuǎn)換為一顆完全二叉樹。任意一個(gè)父節(jié)點(diǎn)大于它的子節(jié)點(diǎn)，這樣的完全二叉樹叫做大頂堆；與之相反的，任意一個(gè)父節(jié)點(diǎn)小于它的子節(jié)點(diǎn)，這樣的完全二叉樹叫做小頂堆。

堆排序的精華就在于把元素個(gè)數(shù)為n的完全二叉樹轉(zhuǎn)換為大頂堆，然后把堆頂和最后一個(gè)元素交換，此時(shí)產(chǎn)生了一個(gè)元素個(gè)數(shù)為n-1的完全二叉樹，然后再轉(zhuǎn)換為大頂堆，繼續(xù)把堆頂和最后一個(gè)元素交換。循環(huán)往復(fù)就實(shí)現(xiàn)了排序。其實(shí)質(zhì)還是選擇排序，每次選出一個(gè)最大的，和最后一個(gè)交換，不過完全二叉樹中選最大元素比遍歷數(shù)組會(huì)快很多。

#include <stdio.h>

void heap_adjust(int arr[], int n) {
 for (int i = n / 2; i >= 1; i--) {
  if (arr[i - 1] < arr[2 * i - 1]) {
   int temp = arr[i - 1];
   arr[i - 1] = arr[2 * i - 1];
   arr[2 * i - 1] = temp;
  }
  if (arr[i - 1] < arr[2 * i] && (2 * i) < n) {
   int temp = arr[i - 1];
   arr[i - 1] = arr[2 * i];
   arr[2 * i] = temp;
  }
 }
}

void heap_sort(int arr[], int array_length) {
 int n = array_length;
 do {
  heap_adjust(arr, n);
  int temp = arr[0];
  arr[0] = arr[n - 1];
  arr[n - 1] = temp;
 } while (n--);
}

void print_array(int arr[], int array_length) {
 for (int i = 0; i < array_length; ++i) {
  printf("%d ", arr[i]);
 }
 printf("\n");
}

int main() {
 int grr[7] = {8, 2, 6, 0, 5, 7, 4};
 heap_sort(grr, 7);
 print_array(grr, 7);
 return 0;
}

歸并排序

歸并的思想在于對復(fù)雜問題的分治，打散到最小長度后然后再進(jìn)行合并操作。假設(shè)有兩個(gè)數(shù)組A、B，指針i指向A的頭部，指針j指向B的頭部，兩邊同時(shí)進(jìn)行遍歷，找到一個(gè)小的就放到數(shù)組里面，對應(yīng)指針后移一位，這樣就能夠保證合并后的數(shù)組是有序的。

#include <stdio.h>
#include <malloc.h>

void merge(int arr[], int start, int mid, int end) {
 int *new_array = (int *) malloc(sizeof(int) * (end - start + 1));
 int i = start;
 int j = mid + 1;
 int k = 0;
 while (i <= mid && j <= end) {
  if (arr[i] < arr[j]) {
   new_array[k++] = arr[i++];
  } else {
   new_array[k++] = arr[j++];
  }
 }
 while (i <= mid) {
  new_array[k++] = arr[i++];
 }
 while (j <= end) {
  new_array[k++] = arr[j++];
 }
 for (int l = 0; l < k; ++l) {
  arr[start + l] = new_array[l];
 }
 free(new_array);
}

void merge_sort(int arr[], int start, int end) {
 int mid = (start + end) / 2;
 if (start >= end) {
  return;
 }
 merge_sort(arr, start, mid);
 merge_sort(arr, mid + 1, end);
 merge(arr, start, mid, end);
}

void print_array(int arr[], int array_length) {
 for (int i = 0; i < array_length; ++i) {
  printf("%d ", arr[i]);
 }
 printf("\n");
}

int main() {
 int hrr[10] = {73, 22, 93, 43, 55, 14, 28, 65, 39, 81};
 merge_sort(hrr, 0, 9);
 print_array(hrr, 10);
 return 0;
}

基數(shù)排序

先按照個(gè)位排序?qū)⑺袛?shù)字分配到0-9這10個(gè)桶里面，然后再按照桶的順序收集起來；再按照十位排序，同樣的步驟……

基礎(chǔ)排序的本質(zhì)是對每一位進(jìn)行排序，對每一位進(jìn)行排序后就能保證這一個(gè)數(shù)整體的大小是按照順序排列的。

#include <stdio.h>
#include <malloc.h>

int get_num(int number, int pos) {
 int num = 0;
 while (pos--) {
  num = number % 10;
  number = number / 10;
 }
 return num;
}

void radix_sort(int arr[], int array_length) {
 int *bucket[10];
 for (int i = 0; i < 10; ++i) {
  bucket[i] = (int *) malloc(sizeof(int) * array_length + 1);
  bucket[i][0] = 0;//桶的第一位保存桶中元素個(gè)數(shù)
 }
 for (int b = 1; b <= 31; ++b) {
  for (int i = 0; i < array_length; ++i) {
   int num = get_num(arr[i], b);//計(jì)算每個(gè)位上的數(shù)字（個(gè)位、十位、百位...）
   int index = ++bucket[num][0];//計(jì)算下標(biāo)
   bucket[num][index] = arr[i];//保存到桶中
  }
  for (int i = 0, k = 0; i < 10; i++) {
   for (int j = 1; j <= bucket[i][0]; ++j) {
    arr[k++] = bucket[i][j];//從桶里面按順序取出來
   }
   bucket[i][0] = 0;//下標(biāo)清零
  }
 }
}

void print_array(int arr[], int array_length) {
 for (int i = 0; i < array_length; ++i) {
  printf("%d ", arr[i]);
 }
 printf("\n");
}

int main() {
 int irr[10] = {73, 22, 93, 43, 55, 14, 28, 65, 39, 81};
 radix_sort(irr, 10);
 print_array(irr, 10);
 return 0;
}