資料結構
網路
關係型資料庫管理系統
作業系統
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+ 次瀏覽
廣告