解释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 ] ==================================================
广告