冒泡排序

选择排序

插入排序

希尔排序

堆排序

归并排序

快速排序

/*排序算法合集*/

#define MAXSIZE 10000
/*交换元素*/
void swap(int* arr, int i, int j) {
	int tmp = arr[i];
	arr[i] = arr[j];
	arr[j] = tmp;
}

/*将两个有序数组合并*/
void _combine(int*src, int* dst, int i, int m, int n) {
	int j;
	int k;
	for (j = m + 1,k=i; j <= n && i <= m; k++) {
		if (src[j] <= src[i])
			dst[k] = src[j++];
		else
			dst[k] = src[i++];
	}
	while (j <= n) {
		dst[k++] = src[j++];
	}
	while (i <= m) {
		dst[k++] = src[i++];
	}
}



/*冒泡排序*/
void bubble_sort(int* arr, int n) {
	int j;
	int flag = 1;
	for (int i = 0; i < n - 1 && flag; i++) {
		flag = 0;
		for (j = n - 1; j > i; j--) {
			if (arr[j] < arr[j - 1]) {
				swap(arr, j, j - 1);
				flag = 1;

			}
		}
	}
}


/*选择排序*/
void select_sort(int* arr, int n) {
	int min;
	int i, j;
	for (i = 0; i < n - 1; i++) {
		min = i;
		for (j = i + 1; j < n; j++) {
			if (arr[j] < arr[min]) {
				min = j;
			}
		}
		if (min != i) {
			swap(arr, min, i);
		}
	}

}


/*插入排序*/
void insert_sort(int* arr, int n) {
	int i, j;
	int tmp;
	for (i = 1; i < n; i++) {
		if (arr[i] < arr[i - 1]) {
			tmp = arr[i];
			for (j = i - 1; j >= 0 && arr[j] > tmp; j--) {
				arr[j + 1] = arr[j];
			}
			arr[j + 1] = tmp;
		}
	}
}


/*希尔排序*/
void shell_sort(int* arr, int n) {
	int i, j;
	int tmp, gap = n;
	do {
		gap = gap / 3 + 1;
		for (i = gap; i < n; i++) {
			if (arr[i] < arr[i - gap]) {
				tmp = arr[i];
				for (j = i - gap; j >= 0 && arr[j] > tmp; j -= gap) {
					arr[j + gap] = arr[j];
				}
				arr[j + gap] = tmp;
			}
		}
	} while (gap > 1);
}


void create_heap(int* arr, int k, int n) {
	int j;
	int tmp = arr[k];
	for (j = 2 * k + 1; j < n; j *= 2) {
		if (j < n - 1 && arr[j] < arr[j + 1])
			++j;
		if (tmp >= arr[j])
			break;
		arr[k] = arr[j];
		k = j;
	}
	arr[k] = tmp;
}
/*堆排序*/
void heap_sort(int* arr, int n) {
	int i;
	for (i = n / 2 - 1; i >= 0; i--)
		create_heap(arr, i, n);
	for (int i = n - 1; i > 0; i--) {
		swap(arr, 0, i);
		create_heap(arr, 0, i - 1);
	}
}

void _merge(int* src, int* dst,int s,int n) {
	if (s == n) {
		dst[s] = src[s];
	}
	else {
		int dst1[MAXSIZE];
		int m = (n + s) / 2;
		_merge(src, dst1, s, m);
		_merge(src, dst1, m + 1, n);
		_combine(dst1, dst, s, m, n);
	}
}
/*归并排序递归*/
void merge_sort(int* arr, int n) {
	_merge(arr, arr, 0, n - 1);
}


_merge_adjust(int* arr, int* tmp, int k, int n) {
	int j;
	for (j = 0; j < n - 2 * k; j += 2 * k) {
		_combine(arr, tmp, j, j + k-1, j+2*k-1);
	}
	while (j < n - k) {
		_combine(arr, tmp, j, j + k-1, n - 1);
	}
	while (j < n) {
		tmp[j] = arr[j++];
	}
}
/*归并排序非递归*/
void merge_sort_no(int* arr, int n) {
	int k=1;
	int tmp[MAXSIZE];
	do {
		_merge_adjust(arr, tmp, k, n);
		k *= 2;
		_merge_adjust(tmp, arr, k, n);
		k *= 2;
	} while (k < n);
}



int  _quick(int* arr, int low, int high) {
	int base = arr[low];
	while (low < high) {
		while (low < high&&arr[high]>=base) {
			high--;
		}
		arr[low] = arr[high];
		while (high >low&&arr[low] <=base) {
			low++;
		}
		arr[high] = arr[low];

	}
	arr[low] = base;
	return low;
}
void _quick_tmp(int* arr,int low, int high) {
	int index;
	if(low < high) {
		index = _quick(arr, low, high);
		_quick_tmp(arr, low, index - 1);
	    _quick_tmp(arr, index + 1, high);
	}
}
/*快速排序*/
void quick_sort(int* arr, int n) {
	_quick_tmp(arr, 0, n - 1);
}

排序算法源码