排序

1.冒泡排序

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];
}