排序
排序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 > arr)
swap(arr, arr);
}
}
}//冒泡排序使用递归的方法实现
void bubblesort2(int* arr, unsigned int len)
{
if (len < 2) return;
for (int i = 0; i < len - 1; i++) {
if (arr > arr) swap(arr, arr);
}
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 < arr) min = j;
}
if (min != i) swap(arr, arr);
}
}//使用非递归的方法，每一轮选出最小的和最大的值，最大的和最后一个元素交换，最小的和第一个元素交换
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 < arr) min = j;
if (arr > arr) max = j;
}
if(i!=min) swap(arr, arr);
if(len-1-i!=max) swap(arr, arr);
}
}//使用递归的方法实现选择排序算法
void selectsort3(int* arr, int len)
{
if (len < 2) return; // 数组小于2个元素不需要排序。
int ii; // 排序的趟数的计数器。
int iminpos = 0; // 每趟循环选出的最小值的位置（数组的下标）。
for (ii = 1; ii < len; ii++)
{
// 找出值更小的元素，记下它的位置。
if (arr < arr)iminpos = ii;
}
// 如果本趟循环的最小的元素不是起始位置的元素，则交换它们的位置。
if (iminpos != 0) swap(arr, arr);
selectsort2(arr + 1, --len);
}3.插入排序
//直接插入排序,对于这个算法，我们可以进行优化，在插入排序的过程中，我们是逐级比对的，
//但是其实前面那个数据系列它是有序的，实际上我们可以通过二分查找法进行查找需要插入的位置，从而达到插入的效果
void insertsort1(int* arr, int len)
{
int i, j;
for ( i = 1; i < len; i++) {
int temp = arr;
for ( j = i - 1; j >= 0; j--) {
if (arr <= temp) break;
arr = arr;
}
//+1是因为最后j还自减了一次
arr = temp;
}
}4. 快速排序
//基于以上的想法，我们对直接插入排序做出改良，改良为二分插入排序
void insertsort2(int* arr, int len)
{
int i, j, low, high, mid;
int temp;
for (i = 1; i < len; i++) {
if (arr < arr) {
temp = arr;
low = 0; high = i - 1;
while (low <= high) {
mid = (low + high) / 2;
if (temp < arr)high = mid - 1;
else low = mid + 1;
}
for (j = i - 1; j >= high + 1; j--) arr = arr;
arr = temp;
}
}
}5. 希尔排序
void Binary_InsertSort(int* arr, int length)
{
int i, j, low, high, mid,temp;
for (i = 1; i < length; i++) {
if (arr < arr) {
temp = arr;
low = 0, high = i - 1;
while (low <= high) {
mid = (low + high) / 2;
if (arr > temp) high = mid - 1;
else low = mid + 1;
}
for (j = i - 1; j >= high + 1; j--) arr = arr;
arr = temp;
}
}
}6.计数排序
//我们要实现快速排序的算法，有递归和非递归两种方法
//我们现在从0开始自己实现了快速排序的算法了。
int partition(int* arr, int low, int high)
{
int i = low;
int pivot = arr;
for (int j = low; j < high; j++) {
if (arr < pivot) swap(arr, arr);
}
swap(arr, arr);
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);
}
}
来源：程序园用户自行投稿发布，如果侵权，请联系站长删除
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！
页:
[1]