排序算法(1)

排序

插入排序

直接插入排序

直接插入排序是O（N^2）的排序算法

从0下标开始往后排

void InsertSort(int* a,int n)//直接插入排序
{for (int i = 0; i < n - 1; i++)//n-1是因为不能数组越界{int emd = i;int tmp = a[emd+1];//保存一下emd的下一个数据防止在循环过程中被覆盖while (emd >= 0)//如果emd大于等于0 那么会遍历一次数组 并且排序{//每次都排序一次if (tmp < a[emd])//如果tmp比a[emd]小那么继续往前找{a[emd + 1] = a[emd];}else//如果tmp比a[emd]大那么跳出循环 //不直接赋值的原因是因为 有可能遍历完数组也没有tmp大的情况{break;}emd--;}a[emd + 1] = tmp;}
}

希尔排序

希尔排序是O（N^1.3）的排序算法
希尔排序的方式是让数组进行预处理让数组接近有序
一般来说 预处理中 每个下标要要跟下标+gap的数组进行对比 如果小于那么交
希尔排序中 进行次数越多 但也到了一定程度也是下降趋势

void ShellSort(int* a, int n)//希尔排序 时间复杂度O(N^1.3)
{//如果 gap = 1 那么就是有序排序int gap = n;//设置预排长度while (gap > 1){gap /= 2;for (size_t i = 0; i < n - gap; i++)//每一组{int end = i;int tmp = a[end + gap];while (end >= 0)//交换一组中需要交换的数据{if (tmp < a[end]){a[end + gap] = a[end];//先换到 end+gap的位置end -= gap;//如果end为负跳出循环 }else{break;}}a[end + gap] = tmp;//因为end变成负数了或者 break了 位置不变}}
}

选择排序

直接选择排序

直接选择排序的O（N^2）的排序算法
直接选择排序是让数据先选出当前一组中的 最小与最大的数 然
后存储起来 最后复赋值到当前一组总最前的位置与最后的位置
需要注意的是当 最小赋值到最前的位置可能 最大的位置在
最前面那个位置 那么就要进行 赋值到原来最小的位置

void SelectSort(int* a, int n)//直接选择排序 O(N^2)
{int begin = 0, end = n - 1;while (begin < end){int min =begin, max = begin;for (size_t i = begin+1; i <=end; i++)//每排一次就确定一次当前排序的最大最小{if (a[i] > a[max]){max = i;}if (a[i] < a[min]){min = i;}}Sawp(&a[begin], &a[min]);if (max == begin)//如果 max == begin的话 min会先跟 begin这个位置换 所以要 赋值到换后min的位置{max = min;}Sawp(&a[end], &a[max]);begin++;end--;}
}

堆排序

堆排序是O（N*logN）的排序算法
堆排序是利用建堆（大堆）并且使用向下排序
为什么使用大堆？
因为如果建小堆 那么堆顶的位置被交换之后 那么这个堆可能就不是个堆了
大堆即使堆顶变了也不影响 其他地方不是堆

向下调整

void AdjustDown(HPDataType* a, int n, int parent)//向下调整
{int child = parent * 2 + 1;while (child < n)//确保这个子树的下标 小于数组大小{if (child + 1 < n&&a[child + 1] < a[child])//child+1这个右子树不存在那么 则直接输出左子树//假设做孩子小 如果比右孩子小的话 ++换成右孩子{++child;}if (a[child] < a[parent])//小孩比父亲大那么交换（大堆）//小的孩子比 父亲小 那么交换（小堆）{Swap(&a[child], &a[parent]);parent = child;child = parent * 2 + 1;}else{break;}}}

堆排序

void HeapSort(HPDataType* a, int n)//堆排序
{int end = n - 1;//向下调整的建大堆//o(n)for (int i = (end-1)/2; i >=0; i--)//i= 父亲节点{AdjustDown(a, n, i);}//向下排序//o(n*log(n))while (end >0){Sawp(&a[0], &a[end]);AdjustDown( a, end, 0);end--;}
}

交换排序

冒泡排序

冒泡排序是O（N^2）的排序算法
冒泡排序是用2次循环然后进行交换

void BubbleSort(int* a, int n)//冒泡排序
{for (int i = 0; i < n; i++){int b = 0;for (int j = 1; j < n-i; j++){if(a[j-1]>a[j])	{Sawp(&a[j-1], &a[j]);b = 1;}}if (b == 0){break;}}
}