排序

排序

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企服之家，中国第一个企服评测及商务社交产业平台。