十大经典算法【C实现】

此篇文章纯属做笔记记录，关于这些经典算法实际上已经算是很经典了。

• 冒泡排序

  算法实现：

  比较相邻的元素。如果第一个比第二个大，就交换他们两个。

  对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。

  针对所有的元素重复以上的步骤，除了最后一个。

  持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

  #define SWITCH    0  //switch 1:递增排序 0:递减排序
  void bubble_sort(int arr[], int len) { int i, j, temp;
          for (i = 0; i < len - 1; i++)
                  for (j = 0; j < len - 1 - i; j++)
                  	{ #if SWITCH
                          if (arr[j] > arr[j + 1]) { //算法实现为递增排序
                          #else
                          if (arr[j] < arr[j + 1]) { //算法实现为递减排序
                          #endif
                                  temp = arr[j];
                                  arr[j] = arr[j + 1];
                                  arr[j + 1] = temp;}
                       }
  }
  

  • 选择排序

    算法实现：

    首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置。

    再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。

    重复第二步，直到所有元素均排序完毕。

    #define SWITCH    0  //switch 1:递增排序 0:递减排序
    //交换两个变量位置 二选一【个人比较喜欢2】
    static void swap(int *a,int *b) 
    { int temp = *a;
        *a = *b;
        *b = temp;
    }
    #define swap(a,b)  {int t=a;a=b;b=t;}
    void selection_sort(int arr[], int len)  
    { int i,j;
        for (i = 0 ; i < len - 1 ; i++) 
        { int min = i;
             for (j = i + 1; j < len; j++)     //继续未排序元素
                { #if SWITCH
                	if (arr[j] < arr[min])    //找到目前最小值 //递增排序
                #else
                	if (arr[j] > arr[min])    //找到目前最小值 //递减排序
                #endif
                	{ min = j;             //记录最小值位置
                	}
                }
              swap(&arr[min], &arr[i]);      //交换值
         }
    }
    

    • 插入排序

      算法实现：将第一待排序序列第一个元素看做一个有序序列，把第二个元素到最后一个元素当成是未排序序列。从头到尾依次扫描未排序序列，将扫描到的每个元素插入有序序列的适当位置。（如果待插入的元素与有序序列中的某个元素相等，则将待插入元素插入到相等元素的后面。）

      #define SWITCH    0  //switch 1:递增排序 0:递减排序
      void insertion_sort(int arr[], int len){ int i,j,key;
              for (i=1;i key = arr[i];
                      j=i-1;
                      #if SWITCH
                      while((j>=0) && (arr[j]>key)) { #else
                      while((j>=0) && (arr[j] #endif
                              arr[j+1] = arr[j];
                              j--;
                      }
                      arr[j+1] = key;
              }
      }
      

      • 希尔排序

        算法实现

        选择一个增量序列 t1，t2，……，tk，其中 ti > tj, tk = 1；按增量序列个数 k，对序列进行 k 趟排序；每趟排序，根据对应的增量 ti，将待排序列分割成若干长度为 m 的子序列，分别对各子表进行直接插入排序。仅增量因子为 1 时，整个序列作为一个表来处理，表长度即为整个序列的长度

        void shell_sort(int arr[], int len) { int gap, i, j;
                int temp;
                for (gap = len >> 1; gap > 0; gap >>= 1)
                        for (i = gap; i < len; i++) { temp = arr[i];
                                for (j = i - gap; j >= 0 && arr[j] > temp; j -= gap)
                                        arr[j + gap] = arr[j];
                                arr[j + gap] = temp;
                        }
        }
        

        • 归并排序

          算法实现：申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列；设定两个指针，最初位置分别为两个已经排序序列的起始位置；比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置；重复步骤 3 直到某一指针达到序列尾；将另一序列剩下的所有元素直接复制到合并序列尾

          #define min(x,y) {x < y ? x : y}
          void merge_sort(int arr[], int len) { int *a = arr;
              int *b = (int *) malloc(len * sizeof(int));
              int seg, start;
              for (seg = 1; seg < len; seg += seg) { for (start = 0; start < len; start += seg * 2) { int low = start, mid = min(start + seg, len), high = min(start + seg * 2, len);
                      int k = low;
                      int start1 = low, end1 = mid;
                      int start2 = mid, end2 = high;
                      while (start1 < end1 && start2 < end2)
                          b[k++] = a[start1] < a[start2] ? a[start1++] : a[start2++];
                      while (start1 < end1)
                          b[k++] = a[start1++];
                      while (start2 < end2)
                          b[k++] = a[start2++];
                  }
                  int *temp = a;
                  a = b;
                  b = temp;
              }
              if (a != arr) { int i;
                  for (i = 0; i < len; i++)
                      b[i] = a[i];
                  b = a;
              }
              free(b);
          }
          

          • 快速排序

            算法实现：

            从数列中挑出一个元素，称为 “基准”（pivot）;重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作；递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序；

            typedef struct _Range { int start, end;
            } Range;
            Range new_Range(int s, int e) { Range r;
                r.start = s;
                r.end = e;
                return r;
            }
            void swap(int *x, int *y) { int t = *x;
                *x = *y;
                *y = t;
            }
            void quick_sort(int arr[], const int len) { if (len <= 0)
                    return; // 避免len等於負值時引發段錯誤（Segment Fault）
                // r[]模擬列表,p為數量,r[p++]為push,r[--p]為pop且取得元素
                Range r[len];
                int p = 0;
                r[p++] = new_Range(0, len - 1);
                while (p) { Range range = r[--p];
                    if (range.start >= range.end)
                        continue;
                    int mid = arr[(range.start + range.end) / 2]; // 選取中間點為基準點
                    int left = range.start, right = range.end;
                    do { while (arr[left] < mid) ++left;   // 檢測基準點左側是否符合要求
                        while (arr[right] > mid) --right; //檢測基準點右側是否符合要求
                        if (left <= right) { swap(&arr[left], &arr[right]);
                            left++;
                            right--;               // 移動指針以繼續
                        }
                    } while (left <= right);
                    if (range.start < right) r[p++] = new_Range(range.start, right);
                    if (range.end > left) r[p++] = new_Range(left, range.end);
                }
            }
            

            • 堆排序

              算法实现：创建一个堆 H[0……n-1]；把堆首（最大值）和堆尾互换；把堆的尺寸缩小 1，并调用 shift_down(0)，目的是把新的数组顶端数据调整到相应位置；重复步骤 2，直到堆的尺寸为 1。

              #include #include void swap(int *a, int *b) { int temp = *b;
                  *b = *a;
                  *a = temp;
              }
              void max_heapify(int arr[], int start, int end) { // 建立父節點指標和子節點指標
                  int dad = start;
                  int son = dad * 2 + 1;
                  while (son <= end) { // 若子節點指標在範圍內才做比較
                      if (son + 1 <= end && arr[son] < arr[son + 1]) // 先比較兩個子節點大小，選擇最大的
                          son++;
                      if (arr[dad] > arr[son]) //如果父節點大於子節點代表調整完畢，直接跳出函數
                          return;
                      else { // 否則交換父子內容再繼續子節點和孫節點比較
                          swap(&arr[dad], &arr[son]);
                          dad = son;
                          son = dad * 2 + 1;
                      }
                  }
              }
              void heap_sort(int arr[], int len) { int i;
                  // 初始化，i從最後一個父節點開始調整
                  for (i = len / 2 - 1; i >= 0; i--)
                      max_heapify(arr, i, len - 1);
                  // 先將第一個元素和已排好元素前一位做交換，再重新調整，直到排序完畢
                  for (i = len - 1; i > 0; i--) { swap(&arr[0], &arr[i]);
                      max_heapify(arr, 0, i - 1);
                  }
              }
              int main() { int arr[] = { 3, 5, 3, 0, 8, 6, 1, 5, 8, 6, 2, 4, 9, 4, 7, 0, 1, 8, 9, 7, 3, 1, 2, 5, 9, 7, 4, 0, 2, 6 };
                  int len = (int) sizeof(arr) / sizeof(*arr);
                  heap_sort(arr, len);
                  int i;
                  for (i = 0; i < len; i++)
                      printf("%d ", arr[i]);
                  printf("\n");
                  return 0;
              }
              

              • 计数排序

                算法实现：找出待排序的数组中最大和最小的元素；统计数组中每个值为i的元素出现的次数，存入数组C的第i项；对所有的计数累加（从C中的第一个元素开始，每一项和前一项相加）；反向填充目标数组：将每个元素i放在新数组的第C(i)项，每放一个元素就将C(i)减去1

                #include #include #include void print_arr(int *arr, int n) { int i;
                        printf("%d", arr[0]);
                        for (i = 1; i < n; i++)
                                printf(" %d", arr[i]);
                        printf("\n");
                }
                void counting_sort(int *ini_arr, int *sorted_arr, int n) { int *count_arr = (int *) malloc(sizeof(int) * 100);
                        int i, j, k;
                        for (k = 0; k < 100; k++)
                                count_arr[k] = 0;
                        for (i = 0; i < n; i++)
                                count_arr[ini_arr[i]]++;
                        for (k = 1; k < 100; k++)
                                count_arr[k] += count_arr[k - 1];
                        for (j = n; j > 0; j--)
                                sorted_arr[--count_arr[ini_arr[j - 1]]] = ini_arr[j - 1];
                        free(count_arr);
                }
                int main(int argc, char **argv) { int n = 10;
                        int i;
                        int *arr = (int *) malloc(sizeof(int) * n);
                        int *sorted_arr = (int *) malloc(sizeof(int) * n);
                        srand(time(0));
                        for (i = 0; i < n; i++)
                                arr[i] = rand() % 100;
                        printf("ini_array: ");
                        print_arr(arr, n);
                        counting_sort(arr, sorted_arr, n);
                        printf("sorted_array: ");
                        print_arr(sorted_arr, n);
                        free(arr);
                        free(sorted_arr);
                        return 0;
                }
                

                • 桶排序

                  算法实现：桶排序是计数排序的升级版。它利用了函数的映射关系，高效与否的关键就在于这个映射函数的确定。为了使桶排序更加高效，我们需要做到这两点：在额外空间充足的情况下，尽量增大桶的数量，使用的映射函数能够将输入的 N 个数据均匀的分配到 K 个桶中

                  #include #define Max_len 10      //数组元素个数
                   
                  // 打印结果
                  void Show(int  arr[], int n)
                  { int i;
                      for ( i=0; i int maxVal = arr[0]; //假设最大为arr[0]
                      
                      for(int i = 1; i < len; i++)  //遍历比较，找到大的就赋值给maxVal
                      { if(arr[i] > maxVal)
                              maxVal = arr[i];
                      }
                      
                      return maxVal;  //返回最大值
                  }
                   
                  //桶排序   参数：数组及其长度
                  void BucketSort(int* arr , int len)
                  { int tmpArrLen = GetMaxVal(arr , len) + 1;
                      int tmpArr[tmpArrLen];  //获得空桶大小
                      int i, j;
                      
                      for( i = 0; i < tmpArrLen; i++)  //空桶初始化
                          tmpArr[i] = 0;
                      
                      for(i = 0; i < len; i++)   //寻访序列，并且把项目一个一个放到对应的桶子去。
                          tmpArr[ arr[i] ]++;
                      
                      for(i = 0, j = 0; i < tmpArrLen; i ++)
                      { while( tmpArr[ i ] != 0) //对每个不是空的桶子进行排序。
                          { arr[j ] = i;  //从不是空的桶子里把项目再放回原来的序列中。
                              j++;
                              tmpArr[i]--;
                          }
                      }
                  }
                   
                  int main()
                  { //测试数据
                      int arr_test[Max_len] = { 8, 4, 2, 3, 5, 1, 6, 9, 0, 7 };
                      
                      //排序前数组序列
                      Show( arr_test, Max_len );
                      //排序
                      BucketSort( arr_test,  Max_len);
                      //排序后数组序列
                      Show( arr_test, Max_len );
                      
                      return 0;
                  }
                  

                  • 基数排序

                    算法实现：基数排序有两种方法：

                    这两种排序算法都利用了桶的概念，但对桶的使用方法上有明显差异：基数排序：根据键值的每位数字来分配桶；计数排序：每个桶只存储单一键值；桶排序：每个桶存储一定范围的数值；

                    #include#define MAX 20
                    //#define SHOWPASS
                    #define BASE 10
                    void print(int *a, int n) { int i;
                      for (i = 0; i < n; i++) { printf("%d\t", a[i]);
                      }
                    }
                    void radixsort(int *a, int n) { int i, b[MAX], m = a[0], exp = 1;
                      for (i = 1; i < n; i++) { if (a[i] > m) { m = a[i];
                        }
                      }
                      while (m / exp > 0) { int bucket[BASE] = { 0 };
                        for (i = 0; i < n; i++) { bucket[(a[i] / exp) % BASE]++;
                        }
                        for (i = 1; i < BASE; i++) { bucket[i] += bucket[i - 1];
                        }
                        for (i = n - 1; i >= 0; i--) { b[--bucket[(a[i] / exp) % BASE]] = a[i];
                        }
                        for (i = 0; i < n; i++) { a[i] = b[i];
                        }
                        exp *= BASE;
                    #ifdef SHOWPASS
                        printf("\nPASS   : ");
                        print(a, n);
                    #endif
                      }
                    }
                    int main() { int arr[MAX];
                      int i, n;
                      printf("Enter total elements (n <= %d) : ", MAX);
                      scanf("%d", &n);
                      n = n < MAX ? n : MAX;
                      printf("Enter %d Elements : ", n);
                      for (i = 0; i < n; i++) { scanf("%d", &arr[i]);
                      }
                      printf("\nARRAY  : ");
                      print(&arr[0], n);
                      radixsort(&arr[0], n);
                      printf("\nSORTED : ");
                      print(&arr[0], n);
                      printf("\n");
                      return 0;
                    }
                    

                    资源参考：

                    还需要完善，写到后面没心情写了，哈哈哈。等有心情就继续