解释C语言中的排序技术


在本文中,我们将学习**不同的排序技术及其在C语言中的实现**。

以下是在C语言和其他编程语言中可以实现的排序技术

使用C语言实现冒泡排序

冒泡排序 是一种基本的排序算法,它通过反复比较相邻元素,必要时交换它们来工作。当不需要交换时,文件就被排序。

使用C语言实现冒泡排序的示例

#include <stdio.h>
void bubbleSort(int array[], int size){
   for(int i = 0; i<size; i++) {
      int swaps = 0; //flag to detect any swap is there or not
      for(int j = 0; j<size-i-1; j++) {
         if(array[j] > array[j+1]) { //when the current item is bigger than next
            int temp;
            temp = array[j];
            array[j] = array[j+1];
            array[j+1] = temp;
            swaps = 1; //set swap flag
         }
      }
      if(!swaps)
         break; // No swap in this pass, so array is sorted
   }
}
int main(){
   int n;
   n = 5;
   int arr[5] = {67, 44, 82, 17, 20}; //initialize an array 
   printf("Array before Sorting: ");
   for(int i = 0; i<n; i++)
      printf("%d ",arr[i]);
   printf("
"); bubbleSort(arr, n); printf("Array after Sorting: "); for(int i = 0; i<n; i++) printf("%d ", arr[i]); printf("
"); }

输出

Array before Sorting: 67 44 82 17 20 
Array after Sorting: 17 20 44 67 82     

使用C语言实现插入排序

插入排序 是一种非常简单的方法,可以将数字按升序或降序排序。这种方法遵循增量方法。可以将其与玩游戏时排序扑克牌的技术进行比较。

使用C语言实现插入排序的示例

#include <stdio.h>
void insertionSort(int array[], int size){
   int key, j;
   for(int i = 1; i<size; i++) {
      key = array[i];//take value
      j = i;
      while(j > 0 && array[j-1]>key) {
         array[j] = array[j-1];
         j--;
      }
      array[j] = key; //insert in right place
   }
}
int main(){
   int n;
   n = 5;
   int arr[5] = {67, 44, 82, 17, 20}; // initialize the array
   printf("Array before Sorting: ");
   for(int i = 0; i<n; i++)
      printf("%d ",arr[i]);
   printf("
"); insertionSort(arr, n); printf("Array after Sorting: "); for(int i = 0; i<n; i++) printf("%d ", arr[i]); printf("
"); }

输出

Array before Sorting: 67 44 82 17 20 
Array after Sorting: 17 20 44 67 82 

使用C语言实现选择排序

选择排序 是一种简单的排序算法。这种排序算法与插入排序一样,是一种原地比较排序算法,其中列表被分成两个部分,排序部分在左侧,未排序部分在右侧。最初,排序部分为空,未排序部分是整个列表。

使用C语言实现选择排序的示例

#include <stdio.h>
void selectionSort(int array[], int size){
   int i, j, imin;
   for(i = 0; i<size-1; i++) {
      imin = i; //get index of minimum data
      for(j = i+1; j<size; j++)
         if(array[j] < array[imin])
            imin = j;
      
      //placing in correct position
      int temp;
      temp = array[i];
      array[i] = array[imin];
      array[imin] = temp;
   }
}
int main(){
   int n;
   n = 5;
   int arr[5] = {12, 19, 55, 2, 16}; // initialize the array
   printf("Array before Sorting: ");
   for(int i = 0; i<n; i++)
      printf("%d ",arr[i]);
   printf("
"); selectionSort(arr, n); printf("Array after Sorting: "); for(int i = 0; i<n; i++) printf("%d ", arr[i]); printf("
"); }

输出

Array before Sorting: 12 19 55 2 16 
Array after Sorting: 2 12 16 19 55 

使用C语言实现归并排序

归并排序 是一种基于分治技术的排序技术。其最坏情况时间复杂度为 Ο(n log n),是使用最广泛和最常用的算法之一。

使用C语言实现归并排序的示例

#include <stdio.h>
#define max 10
int a[11] = { 10, 14, 19, 26, 27, 31, 33, 35, 42, 44, 0 };
int b[10];
void merging(int low, int mid, int high){
   int l1, l2, i;
   for(l1 = low, l2 = mid + 1, i = low; l1 <= mid && l2 <= high; i++) {
      if(a[l1] <= a[l2])
         b[i] = a[l1++];
      else
         b[i] = a[l2++];
   }
   while(l1 <= mid)
      b[i++] = a[l1++];
   while(l2 <= high)
      b[i++] = a[l2++];
   for(i = low; i <= high; i++)
      a[i] = b[i];
}
void sort(int low, int high){
   int mid;
   if(low < high) {
      mid = (low + high) / 2;
      sort(low, mid);
      sort(mid+1, high);
      merging(low, mid, high);
   } else {
      return;
   }
}
int main(){
   int i;
   printf("Array before sorting
"); for(i = 0; i <= max; i++) printf("%d ", a[i]); sort(0, max); printf("
Array after sorting
"); for(i = 0; i <= max; i++) printf("%d ", a[i]); }

输出

Array before sorting
10 14 19 26 27 31 33 35 42 44 0 
Array after sorting
0 10 14 19 26 27 31 33 35 42 44 

使用C语言实现希尔排序

希尔排序 是一种高效的排序算法,基于插入排序算法。该算法避免了插入排序中可能出现的大量移位,如果较小的值位于最右侧并且必须移动到最左侧。

使用C语言实现希尔排序的示例

#include <stdio.h>
void shellSort(int arr[], int n){
   int gap, j, k;
   for(gap = n/2; gap > 0; gap = gap / 2) { //initially gap = n/2, decreasing by gap /2
      for(j = gap; j<n; j++) {
         for(k = j-gap; k>=0; k -= gap) {
            if(arr[k+gap] >= arr[k])
               break;
            else {
               int temp;
               temp = arr[k+gap];
               arr[k+gap] = arr[k];
               arr[k] = temp;
            }
         }
      }
   }
}
int main(){
   int n;
   n = 5;
   int arr[5] = {33, 45, 62, 12, 98}; // initialize the array
   printf("Array before Sorting: ");
   for(int i = 0; i<n; i++)
      printf("%d ",arr[i]);
   printf("
"); shellSort(arr, n); printf("Array after Sorting: "); for(int i = 0; i<n; i++) printf("%d ", arr[i]); printf("
"); }

输出

Array before Sorting: 33 45 62 12 98
Array after Sorting: 12 33 45 62 98    

使用C语言实现堆排序

堆排序 是一种基于堆数据结构的高效排序技术。

使用C语言实现堆排序的示例

#include <stdio.h>
void heapify(int[], int);
void build_maxheap(int heap[], int n){
   int i, j, c, r, t;
   for (i = 1; i < n; i++) {
      c = i;
      do {
         r = (c - 1) / 2;
         if (heap[r] < heap[c]) { // to create MAX heap array
            t = heap[r];
            heap[r] = heap[c];
            heap[c] = t;
         }
         c = r;
      } while (c != 0);
   }
   printf("Heap array: ");
   for (i = 0; i < n; i++)
      printf("%d ", heap[i]);
   heapify(heap, n);
}
void heapify(int heap[], int n){
   int i, j, c, root, temp;
   for (j = n - 1; j >= 0; j--) {
      temp = heap[0];
      heap[0] = heap[j]; // swap max element with rightmost leaf element
      heap[j] = temp;
      root = 0;
      do {
         c = 2 * root + 1; // left node of root element
         if ((heap[c] < heap[c + 1]) && c < j-1)
            c++;
         if (heap[root]<heap[c] && c<j) { // again rearrange to max heap array
            temp = heap[root];
            heap[root] = heap[c];
            heap[c] = temp;
         }
         root = c;
      } while (c < j);
   }
   printf("
The sorted array is: "); for (i = 0; i < n; i++) printf("%d ", heap[i]); } int main(){ int n, i, j, c, root, temp; n = 5; int heap[10] = {2, 3, 1, 0, 4}; // initialize the array build_maxheap(heap, n); }

输出

Heap array: 4 3 1 0 2 
The sorted array is: 0 1 2 3 4 

使用C语言实现桶排序

桶排序 算法类似于计数排序算法,因为它只是计数排序的广义形式。桶排序假设输入元素是从区间 [0, 1) 上的均匀分布中提取的。

使用C语言实现桶排序的示例

#include <stdio.h>
void bucketsort(int a[], int n){ // function to implement bucket sort
   int max = a[0]; // get the maximum element in the array
   for (int i = 1; i < n; i++)
      if (a[i] > max)
         max = a[i];
   int b[max], i;
   for (int i = 0; i <= max; i++) {
      b[i] = 0;
   }
   for (int i = 0; i < n; i++) {
      b[a[i]]++;
   }
   for (int i = 0, j = 0; i <= max; i++) {
      while (b[i] > 0) {
         a[j++] = i;
         b[i]--;
      }
   }
}
int main(){
   int a[] = {12, 45, 33, 87, 56, 9, 11, 7, 67};
   int n = sizeof(a) / sizeof(a[0]); // n is the size of array
   printf("Before sorting array elements are: 
"); for (int i = 0; i < n; ++i) printf("%d ", a[i]); bucketsort(a, n); printf("
After sorting array elements are:
"); for (int i = 0; i < n; ++i) printf("%d ", a[i]); }

输出

Before sorting array elements are: 
12 45 33 87 56 9 11 7 67 
After sorting array elements are: 
7 9 11 12 33 45 56 67 87

使用C语言实现计数排序

计数排序 是一种外部排序算法,假设所有输入值都是介于 0 和 k 之间的整数。然后对这些输入值进行数学计算,将它们放置在输出数组中的正确位置。

使用C语言实现计数排序的示例

#include<stdio.h>
int countingsort(int a[], int n){
   int i, j;
   int output[15], c[100];
   for (i = 0; i < 100; i++)
      c[i] = 0;
   for (j = 0; j < n; j++)
      ++c[a[j]];
   for (i = 1; i <= 99; i++)
      c[i] += c[i-1];
   for (j = n-1; j >= 0; j--) {
      output[c[a[j]] - 1] = a[j];
      --c[a[j]];
   }
   printf("
After sorting array elements are: "); for (i = 0; i<n; i++) printf("%d ", output[i]); } void main(){ int n , i; int a[] = {12, 32, 44, 8, 16}; n = sizeof(a) / sizeof(a[0]); printf("Before sorting array elements are: "); for(int i = 0; i<n; i++){ printf("%d " , a[i]); } countingsort(a, n); }

输出

Before sorting array elements are: 12 32 44 8 16 
After sorting array elements are: 8 12 16 32 44

使用C语言实现基数排序

基数排序 是一种逐步排序算法,从输入元素的最低有效位开始排序。与计数排序和桶排序一样,基数排序也对输入元素做了一些假设,即它们都是 k 位数字。

使用C语言实现基数排序的示例

#include <stdio.h>
void countsort(int a[], int n, int pos){
   int output[n + 1];
   int max = (a[0] / pos) % 10;
   for (int i = 1; i < n; i++) {
      if (((a[i] / pos) % 10) > max)
         max = a[i];
   }
   int count[max + 1];
   for (int i = 0; i < max; ++i)
      count[i] = 0;
   for (int i = 0; i < n; i++)
      count[(a[i] / pos) % 10]++;
   for (int i = 1; i < 10; i++)
      count[i] += count[i - 1];
   for (int i = n - 1; i >= 0; i--) {
      output[count[(a[i] / pos) % 10] - 1] = a[i];
      count[(a[i] / pos) % 10]--;
   }
   for (int i = 0; i < n; i++)
      a[i] = output[i];
}
void radixsort(int a[], int n){
   int max = a[0];
   for (int i = 1; i < n; i++)
      if (a[i] > max)
         max = a[i];
   for (int pos = 1; max / pos > 0; pos *= 10)
      countsort(a, n, pos);
}
int main(){
   int a[] = {236, 15, 333, 27, 9, 108, 76, 498};
   int n = sizeof(a) / sizeof(a[0]);
   printf("Before sorting array elements are: ");
   for (int i = 0; i <n; ++i) {
      printf("%d ", a[i]);
   }
   radixsort(a, n);
   printf("
After sorting array elements are: "); for (int i = 0; i < n; ++i) { printf("%d ", a[i]); } printf("
"); }

输出

Before sorting array elements are: 236 15 333 27 9 108 76 498 
After sorting array elements are: 9 15 27 76 108 236 333 498

使用C语言实现快速排序

快速排序 是一种高效的排序算法,基于将数据数组划分为较小的数组。一个大的数组被划分为两个数组,其中一个数组包含小于指定值(例如枢轴)的值,枢轴是划分的基础,另一个数组包含大于枢轴的值。

使用C语言实现快速排序的示例

#include <stdio.h>
#include <stdbool.h>
#define MAX 7
int intArray[MAX] = {
   4,6,3,2,1,9,7
};
void printline(int count) {
   int i;
   for (i = 0; i < count - 1; i++) {
      printf("=");
   }
   printf("=
"); } void display() { int i; printf("["); // navigate through all items for (i = 0; i < MAX; i++) { printf("%d ", intArray[i]); } printf("]
"); } void swap(int num1, int num2) { int temp = intArray[num1]; intArray[num1] = intArray[num2]; intArray[num2] = temp; } int partition(int left, int right, int pivot) { int leftPointer = left - 1; int rightPointer = right; while (true) { while (intArray[++leftPointer] < pivot) { //do nothing } while (rightPointer > 0 && intArray[--rightPointer] > pivot) { //do nothing } if (leftPointer >= rightPointer) { break; } else { printf(" item swapped :%d,%d
", intArray[leftPointer], intArray[rightPointer]); swap(leftPointer, rightPointer); } } printf(" pivot swapped :%d,%d
", intArray[leftPointer], intArray[right]); swap(leftPointer, right); printf("Updated Array: "); display(); return leftPointer; } void quickSort(int left, int right) { if (right - left <= 0) { return; } else { int pivot = intArray[right]; int partitionPoint = partition(left, right, pivot); quickSort(left, partitionPoint - 1); quickSort(partitionPoint + 1, right); } } int main() { printf("Input Array: "); display(); printline(50); quickSort(0, MAX - 1); printf("Output Array: "); display(); printline(50); }

输出

Input Array: [4 6 3 2 1 9 7 ]
==================================================
 pivot swapped :9,7
Updated Array: [4 6 3 2 1 7 9 ]
 pivot swapped :4,1
Updated Array: [1 6 3 2 4 7 9 ]
 item swapped :6,2
 pivot swapped :6,4
Updated Array: [1 2 3 4 6 7 9 ]
 pivot swapped :3,3
Updated Array: [1 2 3 4 6 7 9 ]
Output Array: [1 2 3 4 6 7 9 ]
==================================================

更新于: 2024年7月3日

34K+ 次浏览

开启您的职业生涯

通过完成课程获得认证

开始学习
广告