排序

1.冒泡排序

<code>void bubblesort1(int* arr, unsigned int len)

{

//长度小于2就不用排序了

if (len < 2) return;

for (int i = 0; i < len - 1; i++) {

for (int j = 0; j < len - 1 - i; j++) {

if (arr[j] > arr[j + 1])

swap(arr[j+1], arr[j]);

}

}

}

//冒泡排序使用递归的方法实现

void bubblesort2(int* arr, unsigned int len)

{

if (len < 2) return;

for (int i = 0; i < len - 1; i++) {

if (arr[i] > arr[i + 1]) swap(arr[i], arr[i + 1]);

}

bubblesort2(arr, --len);

}

2. 选择排序

//使用非递归的方法，每一轮选出最小的值，与第一个元素进行交换

void selectsort1(int* arr, int len)

{

int i = 0, j = 0, min = 0;

for (i = 0; i < len - 1; i++) {

min = i;

for (int j = i + 1; j < len; j++) {

if (arr[j] < arr[min]) min = j;

}

if (min != i) swap(arr[i], arr[min]);

}

}

//使用非递归的方法，每一轮选出最小的和最大的值，最大的和最后一个元素交换，最小的和第一个元素交换

void selectsort2(int* arr, int len)

{

int i = 0, j = 0, min = 0, max = 0;

for (int i = 0; i < len / 2; i++) {

min = i;

max = len - 1 - i;

for (int j = i + 1; j < len - i; j++) {

if (arr[j] < arr[min]) min = j;

if (arr[j] > arr[max]) max = j;

}

if(i!=min) swap(arr[min], arr[i]);

if(len-1-i!=max) swap(arr[max], arr[len - 1 - i]);

}

}

//使用递归的方法实现选择排序算法

void selectsort3(int* arr, int len)

{

if (len < 2) return; // 数组小于2个元素不需要排序。

int ii; // 排序的趟数的计数器。

int iminpos = 0; // 每趟循环选出的最小值的位置（数组的下标）。

for (ii = 1; ii < len; ii++)

{

// 找出值更小的元素，记下它的位置。

if (arr[ii] < arr[iminpos]) iminpos = ii;

}

// 如果本趟循环的最小的元素不是起始位置的元素，则交换它们的位置。

if (iminpos != 0) swap(arr[0], arr[iminpos]);

selectsort2(arr + 1, --len);

}

3.插入排序

//直接插入排序,对于这个算法，我们可以进行优化，在插入排序的过程中，我们是逐级比对的，

//但是其实前面那个数据系列它是有序的，实际上我们可以通过二分查找法进行查找需要插入的位置，从而达到插入的效果

void insertsort1(int* arr, int len)

{

int i, j;

for ( i = 1; i < len; i++) {

int temp = arr[i];

for ( j = i - 1; j >= 0; j--) {

if (arr[j] <= temp) break;

arr[j + 1] = arr[j];

}

//+1是因为最后j还自减了一次

arr[j + 1] = temp;

}

}

//基于以上的想法，我们对直接插入排序做出改良，改良为二分插入排序

void insertsort2(int* arr, int len)

{

int i, j, low, high, mid;

int temp;

for (i = 1; i < len; i++) {

if (arr[i] < arr[i - 1]) {

temp = arr[i];

low = 0; high = i - 1;

while (low <= high) {

mid = (low + high) / 2;

if (temp < arr[mid]) high = mid - 1;

else low = mid + 1;

}

for (j = i - 1; j >= high + 1; j--) arr[j + 1] = arr[j];

arr[high + 1] = temp;

}

}

}

void Binary_InsertSort(int* arr, int length)

{

int i, j, low, high, mid,temp;

for (i = 1; i < length; i++) {

if (arr[i] < arr[i - 1]) {

temp = arr[i];

low = 0, high = i - 1;

while (low <= high) {

mid = (low + high) / 2;

if (arr[mid] > temp) high = mid - 1;

else low = mid + 1;

}

for (j = i - 1; j >= high + 1; j--) arr[j+1] = arr[j];

arr[high + 1] = temp;

}

}

}

4. 快速排序

//我们要实现快速排序的算法，有递归和非递归两种方法

//我们现在从0开始自己实现了快速排序的算法了。

int partition(int* arr, int low, int high)

{

int i = low;

int pivot = arr[high];

for (int j = low; j < high; j++) {

if (arr[j] < pivot) swap(arr[j], arr[i++]);

}

swap(arr[i], arr[high]);

return i;

}

void quicksort(int* arr, int low, int high)

{

if (low < high) {

int mid = partition(arr, low, high);

quicksort(arr, low, mid - 1);

quicksort(arr, mid + 1, high);

}

}

5. 希尔排序

// 希尔排序

void shellsort(int *arr, int len)

{

int i, j, inc, key;

// 初始增量：len/2，每一趟之后除以二

for (inc = len / 2; inc > 0; inc /= 2)

{

// 每一趟采用插入排序

for (i = inc; i < len; i++)

{

key = arr[i];

for (j = i; j >= inc && key < arr[j - inc]; j -= inc)

arr[j] = arr[j - inc];

arr[j] = key;

}

}

}

6.计数排序

//实现计数排序的代码

void countingsort(int arr[], int len)

{

if (len < 1) return;

// 寻找最大的元素

int max = arr[0];

for (size_t i = 1; i < len; i++)

if (arr[i] > max) max = arr[i];

// 分配一个长度为max+1的数组存储计数，并初始化为0

int* count = (int*)malloc(sizeof(int) * (max + 1));

if(count!=NULL) memset(count, 0, sizeof(int) * (max + 1));

// 计数

for (size_t i = 0; i < len; i++)

count[arr[i]]++;

// 统计计数的累计值

for (size_t i = 1; i < max + 1; i++)

count[i] += count[i - 1];

// 创建一个临时数组保存结果

int* output = (int*)malloc(sizeof(int) * len);

// 将元素放到正确的位置上

for (size_t i = 0; i < len; i++)

{

output[count[arr[i]] - 1] = arr[i];

count[arr[i]]--;

}

// 将结果复制回原数组

for (size_t i = 0; i < len; i++)

arr[i] = output[i];

}