日本免费高清视频-国产福利视频导航-黄色在线播放国产-天天操天天操天天操天天操|www.shdianci.com

學無先后，達者為師

網站首頁 編程語言 正文

C語言排序算法實現

作者：Smallcloudy 更新時間： 2022-08-15 編程語言

C語言實現各種排序算法

  • 冒泡排序
  • 選擇排序
  • 插入排序
  • 希爾排序（插入方式）（非交換方式）
  • 快速排序
  • 歸并排序（分治思想）
  • 基數排序（桶排序）
    • 基數排序的基本思想（典型的空間換時間方式）：

冒泡排序

#include <stdio.h>
#include  <stdlib.h>
#include <string.h>

//數組的首地址傳進去
void bubbleSorting(int *arr,int arrLength){

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

int main(){
    int arr[]={3,9,-1,10,20};
    int length = sizeof(arr)/sizeof(int);
    printf("%d\n",length);
    bubbleSorting(arr,length);
    for (int i = 0; i < length; ++i) {
        printf("%d ",arr[i]);
    }
    return 0;
}

選擇排序

#include <stdio.h>
#include  <stdlib.h>
#include <string.h>
void selectedSorting(int* arr,int length){
    //int minNum = INT_MAX;  //整數中的最小值,由于是局部變量，必須賦初值
    for (int i = 0; i < length; ++i) {
        int minNum = INT_MAX;  //整數中的最小值,由于是局部變量，必須賦初值
        int index = 0;
        for (int j = i; j < length; ++j) {
            if(arr[j]<minNum){
                minNum=arr[j];
                index = j;
            }
        }
        //交換位置
        arr[index]=arr[i];
        arr[i]=minNum;
    }
}
int main() {
    int arr[]={8,3,2,1,7,4,6,5};
    selectedSorting(arr, sizeof(arr)/ sizeof(int));
    for (int i = 0; i < sizeof(arr)/ sizeof(int); ++i) {
        printf("%d ",arr[i]);
    }
    return 0;
}

插入排序

#include <stdio.h>
#include  <stdlib.h>
#include <string.h>

void insertionSorting(int* arr,int length){
    for (int i = 1; i < length; ++i) {
        //首先獲取當前元素和索引
        int currentNum = arr[i];
        int currentIndex = i;
        while (currentNum<arr[currentIndex-1] && currentIndex>=0){
            arr[currentIndex]=arr[currentIndex-1];
            currentIndex--;
        }
        arr[currentIndex]=currentNum;
    }
}

int main() {
    int arr[]={8,3,2,1,7,4,6,5};
    insertionSorting(arr, sizeof(arr)/ sizeof(int));
    for (int i = 0; i < sizeof(arr)/ sizeof(int); ++i) {
        printf("%d ",arr[i]);
    }
    printf("hello,world!");
    return 0;
}

希爾排序（插入方式）（非交換方式）

#include <stdio.h>
#include  <stdlib.h>
#include <string.h>


void shellSorting(int* arr,int length){
    for (int gap = length/2; gap >=1 ; gap=gap/2) {
        for (int i = 0; i < length; i=i+gap) {
            int currentNum = arr[i];
            int currentIndex = i;
            while (currentNum<arr[currentIndex-gap] && currentIndex>=0){
                arr[currentIndex]=arr[currentIndex-gap];
                currentIndex=currentIndex-gap;
            }
            arr[currentIndex]=currentNum;
        }
    }
}
int main() {

    int arr[]={8,3,2,1,7,4,6,5};
    shellSorting(arr, sizeof(arr)/ sizeof(int));
    for (int i = 0; i < sizeof(arr)/ sizeof(int); ++i) {
        printf("%d ",arr[i]);
    }
    printf("hello,world!");
    return 0;
}

快速排序

#include <stdio.h>
#include  <stdlib.h>
#include <string.h>

//遞歸形式進行排序，分程左右兩個部分，需要找到一個基準數
void quickSorting(int *arr,int left,int right){
     int l  = left;
     int r  = right;
     //pivot 中軸值
     int pivot = arr[(right+left)/2];
     int temp = 0;

     // while循環的目的是比中軸值小放到左邊， 比中軸值大放到右邊
     while (l<r){
         //左邊先找,找到一個元素
         while (arr[l]<pivot){
             l+=1;
         }

         //右邊先找,找到一個元素
         while (arr[r]>pivot){
             r-=1;
         }

         //如果l>=r說明pivot的左右兩的值，已經交完完成
         if(l>=r){
             break;
         }

         //交換
         temp=arr[l];
         arr[l]=arr[r];
         arr[r]=temp;

         //如果交換完后，發現這個arr[l]==pivot值 相等r--,前移
         if(arr[l]==pivot){
             r-=1;
         }

         //如果交換完后，發現這個arr[r]==pivot值 相等l++,前移
         if(arr[r]==pivot){
             l+=1;
         }

     }

     //如果l==r，必須l++ ,r-- ，否則為出現棧溢出
     //如果是奇數個數字，如果不再走一步，就會在中間相遇，必須錯開中軸值
     if(l==r){
        l+=1;
        r-=1;
     }

     //向左遞歸
     if(left<r){
         quickSorting(arr,left,r);
     }

     //向右遞歸
     if(right>l){
        quickSorting(arr,l,right);
     }

}

int main() {
    int arr[]={8,3,2,1,7,4,6,5};
    quickSorting(arr, 0,(sizeof(arr)/ sizeof(int))-1);
    for (int i = 0; i < sizeof(arr)/ sizeof(int); ++i) {
        printf("%d ",arr[i]);
    }
    printf("hello,world!");
    return 0;
}

歸并排序（分治思想）

在這里插入圖片描述
在這里插入圖片描述

#include <stdio.h>
#include  <stdlib.h>
#include <string.h>

//合并數組
void merge(int* arr,int left,int mid,int right,int *temp){
     int i = left; //初始化i，左邊有序序列的初始索引
     int j = mid+1; //初始化j，右邊有序序列的初始索引
     int t = 0; //指向temp數組的當前索引

     //第一步
     //先把左右兩邊（有序）的數據按照規則填充到temp數組
     //直到左右兩邊的有序序列，有一邊處理完畢
     while (i<=mid && j<=right){
        if(arr[i]<=arr[j]){
            temp[t]=arr[i];
            t+=1;
            i+=1;
        }else{
            temp[t]=arr[j];
            t+=1;
            j+=1;
        }
     }

     //第二步
     //把剩余數據的一邊的數據依次全部填充到temp中
    while (i<=mid){
        temp[t]=arr[i];
        t+=1;
        i+=1;
    }

    while (j<=right){
        temp[t]=arr[j];
        t+=1;
        j+=1;
    }

    //第三步
    //將temp數據拷貝到arr
    //注意，并不是每次都拷貝所有
    t=0;
    int tempLeft =left;
    while (tempLeft<=right){
       arr[tempLeft]=temp[t];
       t+=1;
       tempLeft+=1;
    }
}


/**
 * @param arr 待排序的數組
 * @param left 左索引
 * @param right 右索引
 * @param temp  臨時開辟的數組，用于局部排序和存儲
 */
void mergeSorting(int* arr,int left,int right,int *temp){

    if(left<right){
        int mid = (left+right)/2; //中間索引

        //向左遞歸拆解
        mergeSorting(arr,left,mid,temp);

        //向右遞歸拆解
        mergeSorting(arr,mid+1,right,temp);

        //聚合
        merge(arr,left,mid,right,temp);
    }
}



int main() {
    int arr[]={8,3,2,1,7,4,6,5};
    int temp[sizeof(arr)/ sizeof(int)]={};
    mergeSorting(arr, 0,sizeof(arr)/ sizeof(int),temp);
    for (int i = 0; i < sizeof(arr)/ sizeof(int); ++i) {
        printf("%d ",arr[i]);
    }
    printf("hello,world!");
    return 0;
}

基數排序（桶排序）

在這里插入圖片描述

基數排序的基本思想（典型的空間換時間方式）：

將所有待比較數值統一為同樣的數位長度，數位較短的數前面補零。然后從最低位開始，依次進行一次排序。這樣從最低位排序一直到最高位排序完成后，數列就變成了一個有序序列。

在這里插入圖片描述
在這里插入圖片描述
在這里插入圖片描述

#include <stdio.h>
#include  <stdlib.h>
#include <string.h>
//#define NUMBER 10

void radixSorting(int *arr, int length) {
    char strTemp[] = " ";
    int max = arr[0];
    for (int i = 0; i < length; ++i) {
        if (arr[i] >= max) {
            max = arr[i];
        }
    }
    //得到最大數的是幾位數
    sprintf(strTemp,"%d",max);
    int maxLength = strlen(strTemp);
    //定義一個二維數組，表示10個桶，每個桶就是一個一維數組
    //二維數組包括10個一維數組
    int bucket[10][length];

    //為了記錄每個桶中實際存放了多少個數據，我們定義一個一維數組來記錄每個桶每次放入的數據的個數
    //即bucketElementCounts[0] 代表bucket[0]中存放的個數
    int bucketElementCounts[10]={};

    for (int i = 0,n=1; i < maxLength; ++i,n*=10) {
         //針對每個元素的對應位進行排序處理，第一次是各位，第二次是十位，第三次是百位
        for (int j = 0; j < length; ++j) {
            //取出每個元素對應位的值
            int digitOfElement = arr[j]/n%10;
            //放入到對應的桶中
            bucket[digitOfElement][bucketElementCounts[digitOfElement]]=arr[j];
            bucketElementCounts[digitOfElement]++;
        }

        //按照這個桶的順序（一維數組的下標依次取出數據，放入原來的數組）
        int index =0;
        //遍歷每一桶，并將桶中得數據，放回到原數組
        for (int k = 0; k < sizeof(bucketElementCounts)/ sizeof(int); ++k) {
            //如果桶中有數據，我們才放回到原數組中
            if(bucketElementCounts[k]!=0){
                //循環該桶，即第k個桶（即第k個一維數組），放入
                for (int l = 0; l < bucketElementCounts[k]; ++l) {
                    //取出元素放回到arr
                    arr[index++]=bucket[k][l];
                }
            }

            //取出數據放回后，需要將記錄每個桶的中元素個數的數據清零
            bucketElementCounts[k]=0;
        }
    }
}
int main() {

    int arr[] = {53, 3, 542, 748, 14, 214};
    radixSorting(arr, sizeof(arr)/ sizeof(int));

    for (int i = 0; i < sizeof(arr)/ sizeof(int); ++i) {
        printf("%d ",arr[i]);
    }
    return 0;
}

在這里插入圖片描述
速度較快，但是遇到超大數量級的就不行了。空間不足，容易造成內存溢出。

原文鏈接：https://blog.csdn.net/Smallcloudy/article/details/124886650

欄目分類
最近更新