ToB企服应用市场:ToB评测及商务社交产业平台

标题: 排序 [打印本页]
作者: 飞不高    时间: 2024-7-31 16:38
标题: 排序
排序

1.冒泡排序
  1. void bubblesort1(int* arr, unsigned int len)
  2. {
  3.         //长度小于2就不用排序了
  4.         if (len < 2) return;
  5.         for (int i = 0; i < len - 1; i++) {
  6.                 for (int j = 0; j < len - 1 - i; j++) {
  7.                         if (arr[j] > arr[j + 1])
  8.                                 swap(arr[j+1], arr[j]);
  9.                 }
  10.         }
  12. }
复制代码
  1. //冒泡排序使用递归的方法实现
  2. void bubblesort2(int* arr, unsigned int len)
  3. {
  4.         if (len < 2) return;
  5.         for (int i = 0; i < len - 1; i++) {
  6.                 if (arr[i] > arr[i + 1]) swap(arr[i], arr[i + 1]);
  7.         }
  8.         bubblesort2(arr, --len);
  9. }
复制代码
2. 选择排序
  1. //使用非递归的方法，每一轮选出最小的值，与第一个元素进行交换
  2. void selectsort1(int* arr, int len)
  3. {
  4.         int i = 0, j = 0, min = 0;
  5.         for (i = 0; i < len - 1; i++) {
  6.                 min = i;
  7.                 for (int j = i + 1; j < len; j++) {
  8.                         if (arr[j] < arr[min]) min = j;
  9.                 }
  10.                 if (min != i) swap(arr[i], arr[min]);
  11.         }
  12. }
复制代码
  1. //使用非递归的方法，每一轮选出最小的和最大的值，最大的和最后一个元素交换，最小的和第一个元素交换
  2. void selectsort2(int* arr, int len)
  3. {
  4.         int i = 0, j = 0, min = 0, max = 0;
  5.         for (int i = 0; i < len / 2; i++) {
  6.                 min = i;
  7.                 max = len - 1 - i;
  8.                 for (int j = i + 1; j < len - i; j++) {
  9.                         if (arr[j] < arr[min]) min = j;
  10.                         if (arr[j] > arr[max]) max = j;
  11.                 }
  12.                 if(i!=min) swap(arr[min], arr[i]);
  13.                 if(len-1-i!=max) swap(arr[max], arr[len - 1 - i]);
  14.         }
  15. }
复制代码
  1. //使用递归的方法实现选择排序算法
  2. void selectsort3(int* arr, int len)
  3. {
  4.         if (len < 2) return; // 数组小于2个元素不需要排序。
  6.         int ii;        // 排序的趟数的计数器。
  7.         int iminpos = 0; // 每趟循环选出的最小值的位置（数组的下标）。
  9.         for (ii = 1; ii < len; ii++)
  10.         {
  11.                 // 找出值更小的元素，记下它的位置。
  12.                 if (arr[ii] < arr[iminpos])  iminpos = ii;
  13.         }
  15.         // 如果本趟循环的最小的元素不是起始位置的元素，则交换它们的位置。
  16.         if (iminpos != 0) swap(arr[0], arr[iminpos]);
  18.         selectsort2(arr + 1, --len);
  19. }
复制代码
3.插入排序
  1. //直接插入排序,对于这个算法，我们可以进行优化，在插入排序的过程中，我们是逐级比对的，
  2. //但是其实前面那个数据系列它是有序的，实际上我们可以通过二分查找法进行查找需要插入的位置，从而达到插入的效果
  3. void insertsort1(int* arr, int len)
  4. {
  5.         int i, j;
  6.         for ( i = 1; i < len; i++) {
  7.                 int temp = arr[i];
  8.                 for ( j = i - 1; j >= 0; j--) {
  9.                         if (arr[j] <= temp) break;
  10.                         arr[j + 1] = arr[j];
  11.                 }
  12.                 //+1是因为最后j还自减了一次
  13.                 arr[j + 1] = temp;
  14.         }
  15. }
复制代码
4. 快速排序
  1. //基于以上的想法，我们对直接插入排序做出改良，改良为二分插入排序
  2. void insertsort2(int* arr, int len)
  3. {
  4.         int i, j, low, high, mid;
  5.         int temp;
  6.         for (i = 1; i < len; i++) {
  7.                 if (arr[i] < arr[i - 1]) {
  8.                         temp = arr[i];
  9.                         low = 0; high = i - 1;
  10.                         while (low <= high) {
  11.                                 mid = (low + high) / 2;
  12.                                 if (temp < arr[mid])  high = mid - 1;
  13.                                 else low = mid + 1;
  14.                         }
  15.                         for (j = i - 1; j >= high + 1; j--)   arr[j + 1] = arr[j];
  16.                         arr[high + 1] = temp;
  17.                 }
  18.         }
  19. }
复制代码
5. 希尔排序
  1. void Binary_InsertSort(int* arr, int length)
  2. {
  3.         int i, j, low, high, mid,temp;
  4.         for (i = 1; i < length; i++) {
  5.                 if (arr[i] < arr[i - 1]) {
  6.                         temp = arr[i];
  7.                         low = 0, high = i - 1;
  8.                         while (low <= high) {
  9.                                 mid = (low + high) / 2;
  10.                                 if (arr[mid] > temp)   high = mid - 1;
  11.                                 else low = mid + 1;
  12.                         }
  13.                         for (j = i - 1; j >= high + 1; j--) arr[j+1] = arr[j];
  14.                         arr[high + 1] = temp;
  15.                 }
  16.         }
  17. }
复制代码
6.计数排序
  1. //我们要实现快速排序的算法，有递归和非递归两种方法
  2. //我们现在从0开始自己实现了快速排序的算法了。
  3. int partition(int* arr, int low, int high)
  4. {
  5.     int i = low;
  6.     int pivot = arr[high];
  7.     for (int j = low; j < high; j++) {
  8.         if (arr[j] < pivot) swap(arr[j], arr[i++]);
  9.     }
  10.     swap(arr[i], arr[high]);
  11.     return i;
  12. }
  14. void quicksort(int* arr, int low, int high)
  15. {
  16.     if (low < high) {
  17.         int mid = partition(arr, low, high);
  18.         quicksort(arr, low, mid - 1);
  19.         quicksort(arr, mid + 1, high);
  20.     }
  21. }
复制代码
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。



欢迎光临 ToB企服应用市场:ToB评测及商务社交产业平台 (https://dis.qidao123.com/) Powered by Discuz! X3.4