排序

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