//直接插入排序
void InsertSort(int data[], int n) {
int i, j, temp;
for (i = 1; i < n; i++) { //从第二个元素开始比较
if (data[i] < data[i - 1]) { //后一个元素与前一个元素比较
temp = data[i]; //临时保存较小的值
for (j = i - 1; j >= 0 && data[j] > temp; j--) //往有序序列最后一个元素开始向前找位置
data[j + 1] = data[j]; //元素后移
data[j + 1] = temp; //插入位置
}
}
}
//折半插入排序
void BanInsertSort(int data[], int n) {
int i, j, temp, low, mid, high;
for (i = 1; i < n; i++) {
if (data[i] < data[i - 1]) {
temp = data[i];
low = 0, high = i - 1;
while (low <= high) { //与直接插入的区别是用折半查找的方式在有序序列中找到位置
mid = (low + high) / 2;
if (data[mid] > temp)
high = mid - 1;
else
low = mid + 1;
}
for (j = i - 1; j >= high + 1; j--) //high + 1 最后插入的位置
data[j + 1] = data[j];
data[high + 1] = temp;
}
}
}
//希尔排序
void ShellSort(int data[], int n) {
int temp, j;
for (int d = n / 2; d >= 1; d /= 2) { //确定步长
for (int i = d ; i < n; i++) { //各个小子集内实际上是直接插入排序
if (data[i] < data[i - d]) {
temp = data[i];
for (j = i - d; j >= 0 && data[j] > temp; j -= d)
data[j + d] = data[j];
data[j + d] = temp;
}
}
}
}
//冒泡排序
void swap(int *a, int *b) { //交换元素值
int temp;
temp = *a;
*a = *b;
*b = temp;
}
void BubbleSort(int data[], int n) {
for (int i = 0; i < n - 1; i++) { //冒泡趟数,最多n-1趟
for (int j = n-1; j > i; j--) { //从最后开始向前扫描
if (data[j] < data[j - 1]) //交换
swap(&data[j], &data[j - 1]);
}
}
}
//快速排序
int partition(int data[], int low, int high) {
int pivot = data[low]; //将第一个值作为枢纽值,用pivot暂存
while (low < high) { //扫描
while (low < high && data[high] >= pivot) //先从后扫描,只要扫到比枢纽值小的就交换
high--;
data[low] = data[high];
while (low < high && data[low] <= pivot) //从前往后扫描,只要扫到比枢纽值大的就交换
low++;
data[high] = data[low];
}
data[low] = pivot; //枢纽值的最终位置
return low;
}
void QuickSort(int data[],int low,int high){
if(low<high){
int mid = partition(data,low,high);
QuickSort(data,low,mid-1);
QuickSort(data,mid+1,high);
}
}
//选择排序
void SelectSort(int data[], int n) {
int i, j, min;
for (i = 0; i < n - 1; i++) {
min = i; //暂时将第一个记为最小值
for (j = i + 1; j < n; j++) {
if (data[j] < data[min])
min = j; //更新最小值
}
if(min!=i)
swap(&data[min],&data[i])
}
}
//堆排序
void HeadAdjust(int data[], int i, int n) {
int j;
data[0] = data[i]; //保存根节点
for (j = 2 * i; j <= n; j *= 2) { //从当前节点的左孩子开始比较并进一步向下比较
if (j < n && data[j] < data[j + 1]) //如果左孩子小于右孩子,则右孩子最大
j++;
if (data[0] >= data[j]) //根已最大
break;
else {
data[i] = data[j]; //将最大值上移
i = j; //将此时的孩子看作根节点,便于继续向下调整,看向下调整的结点是否还要继续向下调整
}
}
data[i] = data[0]; //最终位置
}
void BuildMaxHeap(int data[], int n) {
int i;
for (i = n / 2; i > 0; i--) {
HeadAdjust(data, i, n); //反复调整堆
}
}
void swap(int *a, int *b) { //交换元素值
int temp;
temp = *a;
*a = *b;
*b = temp;
}
void HeapSort(int data[], int n) {
BuildMaxHeap(data, 8);
for (int i = n; i > 1; i--) {
swap(&data[i], &data[1]);
HeadAdjust(data, 1, i - 1);
}
}
//归并排序
int *copy = (int *) malloc(8 * sizeof(int));
void Merge(int data[], int low, int mid, int high) {
int i, j, k;
for (k = low; k <= high; k++)
copy[k] = data[k];
for (i = low, j = mid + 1, k = i; i <= mid && j <= high; k++) {
if (copy[i] <= copy[j])
data[k] = copy[i++];
else
data[k] = copy[j++];
}
while (i <= mid)
data[k++] = copy[i++];
while (j <= high)
data[k++] = copy[j++];
}
void MergeSort(int data[], int low, int high) {
if (low < high) {
int mid = (low + high) / 2;
MergeSort(data, low, mid);
MergeSort(data, mid + 1, high);
Merge(data, low, mid, high);
}
}
Last modification:March 23rd, 2021 at 12:45 pm
© The copyright belongs to the author