数据结构
网络
关系型数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法律研究解释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+ 次浏览
广告