本篇博客部分代码实现参考于天勤数据结构，如果有那块代码出现问题，请指出。

文章目录

• 插入排序
• • • 直接插入排序
    • 2-路插入排序
    • 表插入排序
    • 折半插入排序
    • 希尔排序
• 交换排序
• • • 冒泡排序
    • 快速排序
• 选择排序
• • • 简单选择排序
    • 堆排序
• 归并排序
• • • • 二路归并排序
• 基数排序
• • • 基数排序

插入排序

直接插入排序

#include
#include
using namespace std;void InsertSort(int *a, int n){int i, j, temp;for(int i = 1; i < n; i++){temp = a[i];j = i-1;while(j >= 0 && a[j] > temp){a[j+1] = a[j];j--;}a[j+1] = temp;}
}
int main(){int n, a[1000];scanf("%d", &n);for(int i = 0; i < n; i++)scanf("%d", &a[i]);InsertSort(a, n);for(int i = 0; i < n; i++){if(i != 0)printf(" ");printf("%d", a[i]);}printf("\n");return 0;
}
/*
8
49 38 65 97 76 13 27 49*/

2-路插入排序

#include
#include
using namespace std;
//使用循环队列，类似于约瑟夫环
//减少我们正常时候在头部插入的次数
void TwoRoadInsertSort(int *a, int n){int front , rear, que[n];front = rear = 0;que[0] = a[0];for(int i = 1; i < n; i++){if(a[i] >= a[rear]){rear = (rear+1)%n;que[rear] = a[i];}else if(a[i] < a[front]){front = (front-1+n)%n;que[front] = a[i];}else{int pos = (rear+1)%n;//提前保存ear的下一个位置，因为插入一个数，rear一定向后移动1个位置while(a[i] < que[rear]){int temp = (rear+1)%n;que[temp] = que[rear];rear = (rear-1+n) % n;}rear = (rear+1)%n;que[rear] = a[i];rear = pos;}}int i = 0;while(front != rear){a[i++] = que[front];front = (front+1)%n;}
}int main(){int n, a[1000];scanf("%d", &n);for(int i = 0; i < n; i++)scanf("%d", &a[i]);TwoRoadInsertSort(a, n);for(int i = 0; i < n; i++){if(i != 0)printf(" ");printf("%d", a[i]);}printf("\n");return 0;
}
/*
8
49 38 65 97 76 13 27 49*/

表插入排序

#include
#include
using namespace std;
//类似于链表的使用，只不过这个表用的是静态链表
//为了存储方方便我们把数组的作为头
//所以从1开始存储
//经过不断的思考，我选择尾插法实现，
struct Node{int data;int next;
};void TableSort(Node *a, int n){a[0].data = INT_MAX;a[0].next = 1;for(int i = 2; i <= n; i++){int p = a[0].next;int pre = 0;while(a[i].data > a[p].data){pre = p;p = a[p].next;if(p == 0)break;}a[pre].next = i;a[i].next = p;}
}int main(){int n;Node a[1000];scanf("%d", &n);for(int i = 1; i <= n; i++)scanf("%d", &a[i].data);for(int i = 0; i <= n; i++)a[i].next = 0;TableSort(a, n);for(int i = a[0].next; i != 0; i = a[i].next){printf("%d ", a[i].data);}printf("\n");return 0;
}
/*
8
49 38 65 97 76 13 27 49*/

折半插入排序

#include
#include
using namespace std;int BinarySearch(int *a, int l, int r, int k) //使用二分确定范围，确定查找的范围，范围是大于等于的后一个位置
{while(l < r){int mid = l+r >>1;if(a[mid] >= k)r = mid;else l = mid+1;}return l;
}void BinarySort(int *a, int n)
{for(int i = 1; i < n; i++){int temp = a[i];if(temp >= a[i-1])continue;//如果最后当位置大于整体有序的那么就不需要查找了int pos = BinarySearch(a, 0, i-1, temp);cout<<pos<<endl;for(int j = i-1; j >= pos; j--){a[j+1] = a[j];}a[pos] = temp;}
}int main()
{int n, a[1000];scanf("%d", &n);for(int i = 0; i < n; i++)scanf("%d", &a[i]);//InsertSort(a, n);BinarySort(a,n);//int pos = BinarySearch(a, 0, n-1, 39);//cout<for(int i = 0; i < n; i++){if(i != 0)printf(" ");printf("%d", a[i]);}printf("\n");return 0;
}
/*
8
49 38 65 97 76 13 27 49*/

希尔排序

#include
#include
using namespace std;//希尔排序的实现就是利用的之前的插入方法，只不过把之前的i换成了gap,每一次走gap个单位void ShellSort(int *a, int n){for(int gap = n /2; gap > 0; gap /= 2){for(int i = gap; i < n; i += gap){int j = i;while(j-gap >= 0 && a[j] < a[j-gap]){//注意一定是先判断k>= 0 的情况，如果不这么判断如何为－的
//                    a[k+gap] = a[k];     //时候会报错了
//                    k -=   gap;//使用交换的方法更简洁swap(a[j], a[j-gap]);j -= gap;}}}
}int main()
{int n, a[1000];scanf("%d", &n);for(int i = 0; i < n; i++)scanf("%d", &a[i]);ShellSort(a,n);for(int i = 0; i < n; i++){if(i != 0)printf(" ");printf("%d", a[i]);}printf("\n");return 0;
}
/*
8
49 38 65 97 76 13 27 49*/

交换排序

冒泡排序

#include
#include
using namespace std;
//冒泡排序最外层只需要n-1次，n次也行
//先确定最大的泡在最后一个位置
//然后确定第二大的泡在倒数第二个位置
void BubbleSort(int *a, int n){for(int i = 0; i < n-1; i++){for(int j = 0; j < n-1-i; j++){if(a[j] > a[j+1])swap(a[j], a[j+1]);// if(a[i] > a[j])swap(a[i], a[j]);}}}int main()
{int n, a[1000];scanf("%d", &n);for(int i = 0; i < n; i++)scanf("%d", &a[i]);BubbleSort(a,n);for(int i = 0; i < n; i++){if(i != 0)printf(" ");printf("%d", a[i]);}printf("\n");return 0;
}
/*
8
49 38 65 97 76 13 27 49*/

快速排序

#include
#include
using namespace std;
void QuickSort(int *a, int l, int r)
{int i = l, j = r;if(l < r){int temp = a[l];while(i < j){while(i < j && a[j] >= temp)j--;if(i < j)a[i] = a[j], i++;while(i < j && a[i] <= temp)i++;if(i < j)a[j] = a[i], j--;}a[i] = temp;QuickSort(a, l, i-1);QuickSort(a, i+1, r);}
}int main()
{int n, a[1000];scanf("%d", &n);for(int i = 0; i < n; i++)scanf("%d", &a[i]);QuickSort(a,0, n-1);for(int i = 0; i < n; i++){if(i != 0)printf(" ");printf("%d", a[i]);}printf("\n");return 0;
}
/*
8
49 38 65 97 76 13 27 49*/

选择排序

简单选择排序

#include
#include
using namespace std;
void SelectSort(int *a, int n){int i, j, k, temp;for(int i = 0; i < n; i++){k = i;for(int j = i+1; j < n; j++){if(a[k] > a[j])k = j;}if(k != i)swap(a[i], a[k]);}}int main()
{int n, a[1000];scanf("%d", &n);for(int i = 0; i < n; i++)scanf("%d", &a[i]);SelectSort(a,n);for(int i = 0; i < n; i++){if(i != 0)printf(" ");printf("%d", a[i]);}printf("\n");return 0;
}
/*
8
49 38 65 97 76 13 27 49*/

堆排序

#include
#include
using namespace std;
void Sift(int *a, int l, int r){//从1开始int i = l, j = i*2;int temp = a[i];while(j <= r){if(j < r && a[j] < a[j+1])j++;if(a[j] > temp){a[i] = a[j];i = j;j = i*2;}else break;}a[i] = temp;
}
void HeadSort(int *a, int n){for(int i = n / 2; i >= 1; i--)Sift(a, i, n);for(int i = n; i >= 2; i--){swap(a[1], a[i]);Sift(a, 1, i-1);}}
int main()
{int n, a[1000];scanf("%d", &n);for(int i = 1; i <= n; i++)scanf("%d", &a[i]);HeadSort(a, n);for(int i = 1; i <= n; i++){if(i != 1)printf(" ");printf("%d", a[i]);}printf("\n");return 0;
}
/*
8
49 38 65 97 76 13 27 49*/

归并排序

二路归并排序

#include
#include
using namespace std;
void Merge(int *a, int l, int m, int r){int i = l, j = m+1;int temp[r-l+1], k = 0;while(i <= m && j <= r){if(a[i] > a[j])temp[k++] = a[j++];else temp[k++] = a[i++];}while(i <= m)temp[k++] = a[i++];while(j <= r)temp[k++] = a[j++];for(int i = 0; i < k; i++){a[l+i] = temp[i];}
}
void MergeSort(int *a, int l, int r){if(l < r){int mid = l+r>>1;MergeSort(a, l, mid);MergeSort(a, mid+1, r);Merge(a, l, mid, r);}
}
int main()
{int n, a[1000];scanf("%d", &n);for(int i = 0; i < n; i++)scanf("%d", &a[i]);MergeSort(a,0, n-1);for(int i = 0; i < n; i++){if(i != 0)printf(" ");printf("%d", a[i]);}printf("\n");return 0;
}
/*
8
49 38 65 97 76 13 27 49*/

基数排序

基数排序

#include
#include
#include
using namespace std;
void RadixSort(int *a, int n){int max = a[0], base = 1, bucket[20], temp[n];for(int i = 0; i < n; i++)if(a[i] > max)max = a[i];while(max / base > 0){memset(bucket, 0, sizeof bucket);for(int i = 0; i < n; i++){bucket[a[i]/base%10]++;  //确定桶的中数字的个数}for(int i = 1; i < 10; i++)bucket[i] += bucket[i-1];for(int i = n-1; i >= 0; i--){temp[bucket[a[i]/base%10] -1] = a[i];bucket[a[i]/base%10]--;}for(int i = 0; i < n; i++){a[i] = temp[i];}base *= 10;}}int main()
{int n, a[1000];scanf("%d", &n);for(int i = 0; i < n; i++)scanf("%d", &a[i]);RadixSort(a, n);//注意遍历范围[0,n);for(int i = 0; i < n; i++){if(i != 0)printf(" ");printf("%d", a[i]);}printf("\n");return 1;
}
/*
8
49 38 65 97 76 13 27 4910
278 109 63 930 589 184 505 269 8 83*/

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！