c: Sorting Algorithms

SortAlgorithm.h

/*****************************************************************//**
 * \file   SortAlgorithm.h
 * \brief  业务操作方法
 * VSCODE   c11  https://github.com/hustcc/JS-Sorting-Algorithm/blob/master/2.selectionSort.md
 * https://www.programiz.com/dsa/counting-sort
 * https://www.geeksforgeeks.org/sorting-algorithms/
 * \author geovindu,Geovin Du
 * \date   2023-09-19
***********************************************************************/
#ifndef SORTALGORITHM_H
#define SORTALGORITHM_H
  
  
  
   
#include 
#include 
   
/**
 * @brief 1。Bubble Sort冒泡排序法
 * @param data    INT 数组
 * @param lensize   数组长度
 *
 * @return 排序好的数组
 *   
 *   
 */
int* BubbleSort(int* arrdata,int lensize);
   
/**
 * @brief 2 C Program for Selection Sort 选择排序
 * @param arrdata    INT 数组int arrdata[]
 * @param lensize   数组长度
 *
 * @return 返回说明
 *    
 *    
 */
void SelectionSort(int* arrdata, int lensize);
   
/**
 * @brief 3 Insertion Sort插入排序
 * @param arrdata    INT 数组int arrdata[]
 * @param lensize   数组长度
 *
 * @return 返回说明
 *   
 *   
 */
 void InsertionSort(int* arrdata, int lensize);
  
  
  
/**
 * @brief 4 Quick Sort 快速排序
 * @param arrdata    INT 数组
 * @param start   数组长度开始值
 * @param end     数组长度结束值
 * @return 返回说明
 *   
 *   
 */
void QuickSort(int* arrdata, int start, int end);
  
  
/**
 * @brief 5 Merge Sort 合并排序
 * @param arrdata    INT 数组
 * @param start   数组长度开始值
 * @param end     数组长度结束值
 * @return 返回说明
 *   
 *    
 */
void MergeSort(int* arrdata, int const begin, int const end);
  
  
/**
 * @brief 6 Counting Sort 计数排序
 * @param arrdata    INT 数组
 * @param lensize   数组长度
 * @return 返回说明
 *    
 *    
 */
void CountingSort(int* arrdata, int lensize);
  
  
/**
 * @brief 7 Radix Sort 基数排序
 * @param arrdata    INT 数组
 * @param lensize     数组长度
 * @return 返回说明
 *   
 *   
 */
void Radixsort(int* arrdata, int lensize);
  
  
  
  
/**
 * @brief 8 Bucket Sort 桶排序
 * @param arrdata    INT 数组
 * @return 返回说明
 *   
 *   
 */
void BucketSort(int* arrdata);
  
  
  
  
/**
 * @brief 9 Heap Sort 堆排序
 * @param arrdata    INT 数组
 * @return 返回说明
 *    
 *    
 */
void HeapSort(int* arrdata, int lensize);
  
  
/**
 * @brief 10 Shell Sort 希尔排序
 * @param arrdata    INT 数组
 * @param lensize 数组长度
 * @return 返回说明
 *    
 *    
 */
void ShellSort(int* arrdata, int lensize);
  
  
  
   
#endif //SORTALGORITHM_H

SortAlgorithm.c

/*****************************************************************//**
 * \file   SortAlgorithm.c
 * \brief  c Sorting Algorithms 业务操作方法
 * VSCODE   c11  https://stackoverflow.com/questions/71924077/configuring-task-json-and-launch-json-for-c-in-vs-code
 * https://www.programiz.com/dsa/counting-sort
 * https://www.geeksforgeeks.org/sorting-algorithms/
 * 安装插件“Doxygen Documentation Generator”，用来生成注释。
 * 安装插件”C/C++ Snippets”，用来生成文件头、代码块分割线等。
 * \author geovindu,Geovin Du
 * \date   2023-09-19
***********************************************************************/
   
   
#include 
#include 
   
   
#define MAXSIZE 100
  
/**
 * @brief 1。Bubble Sort冒泡排序法
 * @param arrdata    INT 数组
 * @param lensize   数组长度
 *
 * @return 排序好的数组
 *    
 *    
 */
int* BubbleSort(int* arrdata,int lensize)
{
    int i,j,tmp;
    int* newdate;
    /* 原始数据 */
    //int lensize=sizeof(data) / sizeof(data [0]);//sizeof(data); //sizeof(data) / sizeof(data[0]);//
    printf("2共 長度是：%d ",lensize);
    printf("冒泡排序法：\n原始数据为:");
    for (i=0;i
        printf("%3d",arrdata[i]);
    printf("\n");
   
    for (i=(lensize-1);i>=0;i--)     /* 扫描次数 */
    {
        for (j=0;j/*比较、交换次数*/
        {
            if (arrdata[j]>arrdata[j+1])   /* 比较相邻两数，如第一个数较大则交换 */
            {
                tmp=arrdata[j];
                arrdata[j]=arrdata[j+1];
                arrdata[j+1]=tmp;
            }
        }
        printf("第 %d 次排序后的结果是：",lensize-i); /*把各次扫描后的结果打印出来*/
        for (j=0;j
            printf("%3d",arrdata[j]);
        printf("\n");
    }
    //printf("最终排序的结果为：");
    for (i=0;i
        //newdate[i]=data[i];
        printf("%3d",arrdata[i]);
    printf("\n");
   
    return arrdata;
   
}
   
   
void swap(int *a,int *b) //交換兩個變數
{
    int temp = *a;
    *a = *b;
    *b = temp;
}
   
  
/**
 * @brief 2 C Program for Selection Sort 选择排序
 * @param arrdata    INT 数组
 * @param size   数组长度
 *
 * @return 返回说明
 *     -false fail
 *     -true succeedS
 */
void SelectionSort(int* arrdata, int len)
{
    int i,j;
   
        for (i = 0 ; i < len - 1 ; i++)
       {
                int min = i;
                for (j = i + 1; j < len; j++)     //走訪未排序的元素
                        if (arrdata[j] < arrdata[min])    //找到目前最小值
                                min = j;    //紀錄最小值
                swap(&arrdata[min], &arrdata[i]);    //做交換
        }
   
       
   
}
  
  
/**
 * @brief 3 Insertion Sort插入排序
 * @param arrdata    INT 数组int arrdata[]
 * @param size   数组长度
 *
 * @return 返回说明
 *   
 *    
 */
  
void InsertionSort(int* arrdata, int size){
    
    // defining some iterables and variables
    int i, temp, j;
    
    // using the for-loop
    for (i = 1; i < size; i++){
        // initializing the temp variable as value at index i from array
        temp = arrdata[i];
        // initializing another iterable value
        j = i - 1;
        // using the while loop for j >= 0 and arr[j] > temp
        while (j >= 0 && arrdata[j] > temp){
            // swapping the elements
            arrdata[j + 1] = arrdata[j];
            j = j - 1;
        }
        arrdata[j + 1] = temp;
    }
}
  
void qswap(int* a, int* b)
{
    int t = *a;
    *a = *b;
    *b = t;
}
   
  
int partition(int arrdata[], int low, int high)
{
    // Choosing the pivot
    int pivot = arrdata[high];
   
    // Index of smaller element and indicates
    // the right position of pivot found so far
    int qi = (low - 1);
   
    for (int j = low; j <= high - 1; j++) {
   
        // If current element is smaller than the pivot
        if (arrdata[j] < pivot) {           
           qi++;
           qswap(&arrdata[qi], &arrdata[j]);
        }
    }
    qswap(&arrdata[qi + 1], &arrdata[high]);
    return (qi + 1);
}
  
/**
 * @brief 4 Quick Sort 快速排序
 * @param arrdata    INT 数组int arrdata[]
 * @param low   数组长度开始值
 * @param high     数组长度结束值
 * @return 返回说明
 *   
 *   
 */
void QuickSort(int* arrdata, int low, int high){
 if (low < high) {
   
        // pi is partitioning index, arr[p]
        // is now at right place
        int pi = partition(arrdata, low, high);
   
        // Separately sort elements before
        // partition and after partition
        QuickSort(arrdata, low, pi - 1);
        QuickSort(arrdata, pi + 1, high);
    }
}
  
  
void merge(int array[], int const left, int const mid,
           int const right)
{
    int const subArrayOne = mid - left + 1;
    int const subArrayTwo = right - mid;
   
    // Create temp arrays
    int* leftArray =(int*)malloc(subArrayOne);// int [subArrayOne];
    int* rightArray = (int*)malloc(subArrayTwo);//int [subArrayTwo];
   
    // Copy data to temp arrays leftArray[] and rightArray[]
    for (int i = 0; i < subArrayOne; i++)
        leftArray[i] = array[left + i];
    for (int j = 0; j < subArrayTwo; j++)
        rightArray[j] = array[mid + 1 + j];
   
    int indexOfSubArrayOne = 0;
    int indexOfSubArrayTwo = 0;
    int indexOfMergedArray = left;
   
    // Merge the temp arrays back into array[left..right]
    while (indexOfSubArrayOne < subArrayOne
           && indexOfSubArrayTwo < subArrayTwo) {
        if (leftArray[indexOfSubArrayOne]
            <= rightArray[indexOfSubArrayTwo]) {
            array[indexOfMergedArray]
                = leftArray[indexOfSubArrayOne];
            indexOfSubArrayOne++;
        }
        else {
            array[indexOfMergedArray]
                = rightArray[indexOfSubArrayTwo];
            indexOfSubArrayTwo++;
        }
        indexOfMergedArray++;
    }
   
    // Copy the remaining elements of
    // left[], if there are any
    while (indexOfSubArrayOne < subArrayOne) {
        array[indexOfMergedArray]
            = leftArray[indexOfSubArrayOne];
        indexOfSubArrayOne++;
        indexOfMergedArray++;
    }
   
    // Copy the remaining elements of
    // right[], if there are any
    while (indexOfSubArrayTwo < subArrayTwo) {
        array[indexOfMergedArray]
            = rightArray[indexOfSubArrayTwo];
        indexOfSubArrayTwo++;
        indexOfMergedArray++;
    }
  
    //delete[] leftArray;
      
    //delete[] rightArray;
}
   
/**
 * @brief 5 Merge Sort 合并/归并排序
 * @param arrdata    INT 数组
 * @param start   数组长度开始值
 * @param end     数组长度结束值
 * @return 返回说明
 *    
 *    
 */
void MergeSort(int* arrdata, int const begin, int const end)
{
    if (begin >= end)
        return;
   
    int mid = begin + (end - begin) / 2;
    MergeSort(arrdata, begin, mid);
    MergeSort(arrdata, mid + 1, end);
    merge(arrdata, begin, mid, end);
}
  
/**
 * @brief 6 Counting Sort 计数排序
 * @param arrdata    INT 数组
 * @param size   数组长度
 * @return 返回说明
 *    
 *    
 */
void CountingSort(int* arrdata, int size) {
  int output[10];
  
  // Find the largest element of the array
  int max = arrdata[0];
  for (int i = 1; i < size; i++) {
    if (arrdata[i] > max)
      max = arrdata[i];
  }
  
  // The size of count must be at least (max+1) but
  // we cannot declare it as int count(max+1) in C as
  // it does not support dynamic memory allocation.
  // So, its size is provided statically.
  int count[10];
  
  // Initialize count array with all zeros.
  for (int i = 0; i <= max; ++i) {
    count[i] = 0;
  }
  
  // Store the count of each element
  for (int i = 0; i < size; i++) {
    count[arrdata[i]]++;
  }
  
  // Store the cummulative count of each array
  for (int i = 1; i <= max; i++) {
    count[i] += count[i - 1];
  }
  
  // Find the index of each element of the original array in count array, and
  // place the elements in output array
  for (int i = size - 1; i >= 0; i--) {
    output[count[arrdata[i]] - 1] = arrdata[i];
    count[arrdata[i]]--;
  }
  
  // Copy the sorted elements into original array
  for (int i = 0; i < size; i++) {
    arrdata[i] = output[i];
  }
}
  
  
int getMax(int array[], int n) {
  int max = array[0];
  for (int i = 1; i < n; i++)
    if (array[i] > max)
      max = array[i];
  return max;
}
  
void radcountingSort(int array[], int size, int place) {
  int output[size + 1];
  int max = (array[0] / place) % 10;
  
  for (int i = 1; i < size; i++) {
    if (((array[i] / place) % 10) > max)
      max = array[i];
  }
  int count[max + 1];
  
  for (int i = 0; i < max; ++i)
    count[i] = 0;
  
  // Calculate count of elements
  for (int i = 0; i < size; i++)
    count[(array[i] / place) % 10]++;
      
  // Calculate cumulative count
  for (int i = 1; i < 10; i++)
    count[i] += count[i - 1];
  
  // Place the elements in sorted order
  for (int i = size - 1; i >= 0; i--) {
    output[count[(array[i] / place) % 10] - 1] = array[i];
    count[(array[i] / place) % 10]--;
  }
  
  for (int i = 0; i < size; i++)
    array[i] = output[i];
}
  
  
/**
 * @brief 7 Radix Sort 基数排序
 * @param arrdata    INT 数组
 * @param size   数组长度
 * @return 返回说明
 *    
 *   
 */
void Radixsort(int* arrdata, int size) {
  // Get maximum element
  int max = getMax(arrdata, size);
  
  // Apply counting sort to sort elements based on place value.
  for (int place = 1; max / place > 0; place *= 10)
    radcountingSort(arrdata, size, place);
}
  
//这个数是有规则的
#define NARRAY 9   // Array size 7
#define NBUCKET 8  // Number of buckets  6
#define INTERVAL 12  // Each bucket capacity  10
  
  
struct Node {
  int data;
  struct Node *next;
};
  
struct Node *BucketInsertionSort(struct Node *list);
//void printBuckets(struct Node *list);
  
int getBucketIndex(int value);
  
  
/**
 * @brief 8 Radix Sort 基数排序
 * @param arrdata    INT 数组
 * @return 返回说明
 *     -false fail
 *     -true succeed
 */
void BucketSort(int* arrdata) {
  int i, j;
  struct Node **buckets;
  
  // Create buckets and allocate memory size
  buckets = (struct Node **)malloc(sizeof(struct Node *) * NBUCKET);
  
  // Initialize empty buckets
  for (i = 0; i < NBUCKET; ++i) {
    buckets[i] = NULL;
  }
  
  // Fill the buckets with respective elements
  for (i = 0; i < NARRAY; ++i) {
    struct Node *current;
    int pos = getBucketIndex(arrdata[i]);
    current = (struct Node *)malloc(sizeof(struct Node));
    current->data = arrdata[i];
    current->next = buckets[pos];
    buckets[pos] = current;
  }
  
  // Print the buckets along with their elements
  //for (i = 0; i < NBUCKET; i++) {
    //printf("Bucket[%d]: ", i);
    //printBuckets(buckets[i]);
    //printf("\n");
  //}
  
  // Sort the elements of each bucket
  for (i = 0; i < NBUCKET; ++i) {
    buckets[i] = BucketInsertionSort(buckets[i]);
  }
  
  //printf("-------------\n");
  //printf("Bucktets after sorting\n");
 // for (i = 0; i < NBUCKET; i++) {
    //printf("Bucket[%d]: ", i);
    //printBuckets(buckets[i]);
    //printf("\n");
 // }
  
  // Put sorted elements on arr
  for (j = 0, i = 0; i < NBUCKET; ++i) {
    struct Node *node;
    node = buckets[i];
    while (node) {
      arrdata[j++] = node->data;
      node = node->next;
    }
  }
  
  return;
}
  
  
struct Node* BucketInsertionSort(struct Node *list) {
  struct Node *k, *nodeList;
  if (list == 0 || list->next == 0) {
    return list;
  }
  
  nodeList = list;
  k = list->next;
  nodeList->next = 0;
  while (k != 0) {
    struct Node *ptr;
    if (nodeList->data > k->data) {
      struct Node *tmp;
      tmp = k;
      k = k->next;
      tmp->next = nodeList;
      nodeList = tmp;
      continue;
    }
  
    for (ptr = nodeList; ptr->next != 0; ptr = ptr->next) {
      if (ptr->next->data > k->data)
        break;
    }
  
    if (ptr->next != 0) {
      struct Node *tmp;
      tmp = k;
      k = k->next;
      tmp->next = ptr->next;
      ptr->next = tmp;
      continue;
    } else {
      ptr->next = k;
      k = k->next;
      ptr->next->next = 0;
      continue;
    }
  }
  return nodeList;
}
  
int getBucketIndex(int value) {
  return value / INTERVAL;
}
  
void printBuckets(struct Node *list) {
  struct Node *cur = list;
  while (cur) {
    printf("%d ", cur->data);
    cur = cur->next;
  }
}
  
  
void heapify(int arr[], int n, int i) {
    // Find largest among root, left child and right child
    int largest = i;
    int left = 2 * i + 1;
    int right = 2 * i + 2;
    
    if (left < n && arr[left] > arr[largest])
      largest = left;
    
    if (right < n && arr[right] > arr[largest])
      largest = right;
    
    // Swap and continue heapifying if root is not largest
    if (largest != i) {
      swap(&arr[i], &arr[largest]);
      heapify(arr, n, largest);
    }
  }
  
  
/**
 * @brief 9 Heap Sort 堆排序
 * @param arrdata    INT 数组
 * @return 返回说明
 *   
 *   
 */
void HeapSort(int* arrdata, int n) {
    // Build max heap
    for (int i = n / 2 - 1; i >= 0; i--)
      heapify(arrdata, n, i);
    
    // Heap sort
    for (int i = n - 1; i >= 0; i--) {
      swap(&arrdata[0], &arrdata[i]);
    
      // Heapify root element to get highest element at root again
      heapify(arrdata, i, 0);
    }
}
    
/**
 * @brief 10 Shell Sort 希尔排序
 * @param arrdata    INT 数组
 * @param n 数组长度
 * @return 返回说明
 *   
 *    
 */
void ShellSort(int* arrdata, int n) {
  // Rearrange elements at each n/2, n/4, n/8, ... intervals
 for (int gap = n/2; gap > 0; gap /= 2)
    {
        // Do a gapped insertion sort for this gap size.
        // The first gap elements a[0..gap-1] are already in gapped order
        // keep adding one more element until the entire array is
        // gap sorted
        for (int i = gap; i < n; i += 1)
        {
            // add a[i] to the elements that have been gap sorted
            // save a[i] in temp and make a hole at position i
            int temp = arrdata[i];
    
            // shift earlier gap-sorted elements up until the correct
            // location for a[i] is found
            int j;          
            for (j = i; j >= gap && arrdata[j - gap] > temp; j -= gap)
                arrdata[j] = arrdata[j - gap];
                
            //  put temp (the original a[i]) in its correct location
            arrdata[j] = temp;
        }
    }
      
  
  /*
  for (int interval = n / 2; interval > 0; interval /= 2) {
    for (int i = interval; i < n; i += 1) {
      int temp = array[i];
      int j;
      for (j = i; j >= interval && array[j - interval] > temp; j -= interval) {
        array[j] = array[j - interval];
      }
      array[j] = temp;
    }
  }
  */
}

调用：

/*
 * @Author: 涂聚文 geovindu,Geovin Du
 * @Date: 2023-09-11 14:07:29
 * @LastEditors:
 * @LastEditTime: 2023-09-20 14:35:49
 * @FilePath: \testcpp\helloword.c
 * @Description:
 */
/*****************************************************************//**
 * \file   helloworld.C
 * \brief  业务操作方法
 * VSCODE   c11         安装插件“Doxygen Documentation Generator”，用来生成注释。
                        安装插件”C/C++ Snippets”，用来生成文件头、代码块分割线等。KoroFileHeader
                        C/C++ Snippets插件设置
 * \author geovindu,Geovin Du
 * \date   2023-09-19
***********************************************************************/
 
#include
#include
#include
#include "include/SortAlgorithm.h"
 
 
int main()
{
    printf("hello world, c \n");
    printf("你好，中国\n");
 
 
    int i;
    int *p;  
    char str[20];
    //1冒泡排序
    int data[12]={60,50,39,27,12,8,45,63,20,2,10,88};   /* 原始数据 */
    int lensize=sizeof(data) / sizeof(data [0]);//sizeof(data);
    p=BubbleSort(data,lensize);
      
    //itoa(lensize, str, 10);
    //printf("1共長度是 %d ",lensize);
      
    printf("\n1冒泡排序的结果为:");
    for (i=0;i
        printf("%3d",p[i]);
    printf("\n");
    //2选择排序
    int arr[] = { 64, 25, 12, 22, 11,88,28,100 };
    int n = sizeof(arr) / sizeof(arr[0]);
    selectionSort(arr, n);
    int ii;
    printf("2选择排序结果为:");
    for(ii = 0; ii < n; ii++)
        printf("%d ", arr[ii]);
    printf("\n");
    //3插入排序
     int inarr[] = {25, 23, 28, 16, 18,100,8,99}; 
   
    // calculating the size of array 
    int size = sizeof(inarr) / sizeof(inarr[0]); 
    printf("3插入排序结果为:");
    InsertionSort(inarr, size); 
        for(ii = 0; ii < n; ii++)
        printf("%d ", inarr[ii]);
    printf("\n");
 
    //4快速排序
    // defining and initializing an array 
    int qsarr[] = {100,25, 23, 28, 16, 18,8,99,3,20};
    printf("4快速排序结果为:");
    // calculating the size of array 
    size = sizeof(qsarr) / sizeof(qsarr[0]); 
    QuickSort(qsarr, 0, size - 1); 
    for (int i = 0; i < size; i++)
        printf("%d ", qsarr[i]);
    printf("\n");
    //5 合并排序
    printf("5合并排序结果为:");
    int mearr[] = { 12, 11, 23, 55, 6, 57,3,100,9 };
    int arr_size = sizeof(mearr) / sizeof(mearr[0]);
    MergeSort(mearr, 0, arr_size - 1);
    for (int i = 0; i < arr_size; i++)
        printf("%d ", mearr[i]);
    printf("\n");
 
    //6 计数排序
    printf("6计数排序结果为:");
    int carray[] = {4, 2, 2, 8, 3, 3, 1};
    int cn = sizeof(carray) / sizeof(carray[0]);
    CountingSort(carray, cn);
    for (int i = 0; i < cn; i++)
        printf("%d ", carray[i]);
    printf("\n");
 
    //7. 基数排序
    printf("7基数排序结果为:");
    int rarray[] = {121, 432, 564, 23, 1, 45, 788};
    int rn = sizeof(rarray) / sizeof(rarray[0]);
    Radixsort(rarray, rn);
    for (int i = 0; i < rn; i++)
        printf("%d ", rarray[i]);
    printf("\n");
 
    //8 Bucket Sort 桶排序
    printf("8桶排序结果为:");
    int barray[] = {42, 32, 33, 5,52, 37,100, 47, 51};
    BucketSort(barray);
    int bn = sizeof(barray) / sizeof(barray[0]);
    for (int i = 0; i < bn; i++)
        printf("%d ", barray[i]);
    printf("\n");
    //9堆排序
    printf("9堆排序结果为:");
    int harr[] = {1, 12, 9, 5, 6, 10};
    int hn = sizeof(harr) / sizeof(harr[0]); 
    HeapSort(harr, hn);
    for (int i = 0; i < hn; i++)
        printf("%d ", harr[i]);
    printf("\n");
 
    //10.希尔排序
    printf("10.希尔排序结果为:");
    int sdata[] = {9, 8, 3, 7, 25, 6, 4, 11,38};
    int ssize = sizeof(sdata) / sizeof(sdata[0]);
    ShellSort(sdata, ssize);
    for (int i = 0; i < ssize; i++)
        printf("%d ", sdata[i]);
    printf("\n");
 
 
 
 
 
    //system("pause");  liunx 无效，win 下使用
    return 0;
     
}