面试官爱问的10大经典排序算法,20+张图来搞定
Hollis
共 397字,需浏览 1分钟
·
2020-10-31 01:50
冒泡排序
简介
浮
到数列的顶端,就如同碳酸饮料中二氧化碳的气泡最终会上浮到顶端一样,故名冒泡排序。复杂度与稳定性
思路原理
从第一个元素开始一个一个的比较相邻的元素,如果第一个比第二个大即 a[1]>a[2]
,就彼此交换。从第一对到最后一对,对每一对相邻元素做一样的操作。此时在最后的元素应该会是最大的数,我们也称呼 一遍这样的操作
为一趟冒泡排序。针对所有的元素重复以上的步骤,每一趟得到的最大值已放在最后,下一次操作则不需要将此最大值纳入计算。 持续对每次对越来越少的元素,重复上面的步骤。 直到所有的数字都比较完成符合 a[i]
,即完成冒泡排序。
图示过程
主要代码实现
void bubble_sort(int a[],int n) {
for(int i=0; ifor(int j=0; j if(a[j]>a[j+1]) {
swap(a[j],a[j+1]); //交换数据
}
}
}
}
namespace std
命名空间的使用,std自带了交换函数swap(a,b)
,可以直接使用,其功能是交换a与b的两个值,当然你可以自定义swap函数,其模板代码为:template //模板类,可以让参数为任意类型
void swap(T &a,T &b) {
T c(a);
a=b;
b=c;
}
void swap(int &a, int &b) { //指定类型
int temp = a;
a = b;
b = temp;
}
选择排序
简介
复杂度与稳定性
过程介绍(以顺序为例)
首先设置两个记录i和j,i从数组第一个元素开始,j从(i+1)个元素开始。 接着j遍历整个数组,选出整个数组最小的值,并让这个最小的值和i的位置交换。 i选中下一个元素(i++),重复进行每一趟选择排序。 持续上述步骤,使得i到达(n-1)处,即完成排序 。
图示过程:
代码实现
void select_sort(int a[],int n){
int temp;
for(int i=0;itemp=i; //利用一个中间变量temp来记录需要交换元素的位置
for(int j=i+1;jif(a[temp]>a[j]){ //选出待排数据中的最小值
temp=j;
}
}
swap(a[i],a[temp]); //交换函数
}
}
插入排序
简介
复杂度与稳定性
过程介绍
每次从无序表中取出第一个元素,把它插入到有序表的合适位置,使有序表仍然有序。 第一趟比较前两个数,然后把第二个数按大小插入到有序表中; 第二趟把第三个数据与前两个数从后向前扫描,把第三个数按大小插入到有序表中; 依次进行下去,进行了(n-1)趟扫描以后就完成了整个排序过程。
图示过程
代码实现
void insert_sort(int a[],int n) {
int i,j;
//外层循环标识并决定待比较的数值
for(i=1; iif(a[i] int temp=a[i];
//待比较数值确定其最终位置
for(j=i-1; j>=0 && a[j]>temp; j--) {
a[j+1]=a[j];
}
a[j+1]=temp;//此处就是a[j+1]=temp;
}
}
}
希尔排序
简介
缩小增量排序
,是直接插入排序算法的一种更高效的改进版本。复杂度与稳定性
过程介绍
选择一个增量序列 t1,t2,……,tk,其中 ti > tj, tk = 1; 按增量序列个数 k,对序列进行 k 趟排序; 每趟排序,根据对应的增量 ti,将待排序列分割成若干长度为 m 的子序列,分别对各子表进行直接插入排序。 仅增量因子为 1 时,整个序列作为一个表来处理,表长度即为整个序列的长度。
图示过程
主要代码实现
void shellSort(int arr[], int n) {
int i, j, gap;
for (gap = n / 2; gap > 0; gap /= 2) {
for (i = 0; i < gap; i++) {
for (j = i + gap; j < n; j += gap) {
for (int k = j; k > i && arr[k] < arr[k-gap]; k -= gap) {
swap(arr[k-gap], arr[k]);
}
}
}
}
}
堆排序
简介
复杂度与稳定性
什么是堆?
大顶堆:每个结点的值都大于或等于其左右孩子结点的值 小顶堆:每个结点的值都小于或等于其左右孩子结点的值
过程介绍
主要代码实现
/* Function: 交换交换根节点和数组末尾元素的值*/
void Swap(int *heap, int len) {
int temp;
temp = heap[0];
heap[0] = heap[len-1];
heap[len-1] = temp;
}
/* Function: 构建大顶堆 */
void BuildMaxHeap(int *heap, int len) {
int i,temp;
for (i = len/2-1; i >= 0; i--) {
if ((2*i+1) < len && heap[i] < heap[2*i+1]) { /* 根节点大于左子树 */
temp = heap[i];
heap[i] = heap[2*i+1];
heap[2*i+1] = temp;
/* 检查交换后的左子树是否满足大顶堆性质 如果不满足 则重新调整子树结构 */
if ((2*(2*i+1)+1 < len && heap[2*i+1] < heap[2*(2*i+1)+1]) || (2*(2*i+1)+2 < len && heap[2*i+1] < heap[2*(2*i+1)+2])) {
BuildMaxHeap(heap, len);
}
}
if ((2*i+2) < len && heap[i] < heap[2*i+2]) { /* 根节点大于右子树 */
temp = heap[i];
heap[i] = heap[2*i+2];
heap[2*i+2] = temp;
/* 检查交换后的右子树是否满足大顶堆性质 如果不满足 则重新调整子树结构 */
if ((2*(2*i+2)+1 < len && heap[2*i+2] < heap[2*(2*i+2)+1]) || (2*(2*i+2)+2 < len && heap[2*i+2] < heap[2*(2*i+2)+2])) {
BuildMaxHeap(heap, len);
}
}
}
}
归并排序
简介
复杂度与稳定性
过程介绍
申请空间,使其大小为两个已经排序序列之和,该空间用来存放合并后的序列 设定两个指针,最初位置分别为两个已经排序序列的起始位置 比较两个指针所指向的元素,选择相对小的元素放入到合并空间,并移动指针到下一位置 重复步骤c直到某一指针超出序列尾 将另一序列剩下的所有元素直接复制到合并序列尾
图示过程
主要代码实现
void merge(int arr[],int l,int mid,int r) {
int aux[r-l+1];//开辟一个新的数组,将原数组映射进去
for(int m=l; m<=r; m++) {
aux[m-l]=arr[m];
}
int i=l,j=mid+1;//i和j分别指向两个子数组开头部分
for(int k=l; k<=r; k++) {
if(i>mid) {
arr[k]=aux[j-l];
j++;
} else if(j>r) {
arr[k]=aux[i-l];
i++;
} else if(aux[i-l]-l ]) {
arr[k]=aux[i-l];
i++;
} else {
arr[k]=aux[j-l];
j++;
}
}
}
void merge_sort(int arr[],int n) {
for(int sz=1; sz<=n; sz+=sz) {
for(int i=0; i+sz//对局部:arr[i...sz-1]和arr[i+sz.....i+2*sz-1]进行排序
merge(arr,i,i+sz-1,min(i+sz+sz-1,n-1)); //min函数防止越界
}
}
}
快速排序
简介
复杂度与稳定性
过程介绍
在数组中选择一个基准点 分别从数组的两端扫描数组,设两个指示标志 从后半部分开始,如果发现有元素比该基准点的值小,就交换位置 然后从前半部分开始扫描,发现有元素大于基准点的值,继续交换位置 如此往复循环,然后把基准点的值放到high这个位置,排序完成
图示过程
主要代码实现
void qucik_sort(int a[],int low,int high) {
int i,j,temp;
i=low;
j=high;
if(lowtemp=a[low]; //设置枢轴
while(i!=j) {
while(j>i&&a[j]>=temp) {
--j;
}
if(ia[i]=a[j];
++i;
}
while(i++i;
}
if(ia[j]=a[i];
--j;
}
}
a[i]=temp;
qucik_sort(a,low,i-1);
qucik_sort(a,i+1,high);
}
}
计数排序
简介
O(k)>O(n*log(n))
的时候其效率反而不如基于比较的排序。复杂度与稳定性
过程介绍
找出待排序的数组中最大和最小的元素 统计数组中每个值为i的元素出现的次数,存入数组C的第i项 对所有的计数累加(从C中的第一个元素开始,每一项和前一项相加) 反向填充目标数组:将每个元素i放在新数组的第C(i)项,每放一个元素就将C(i)减去1
图示过程
代码实现
#include
#include
#include
void CountSort(int *arr, int len){
if(arr == NULL) return;
int max = arr[0], min = arr[0];
for(int i = 1; i < len; i++){
if(arr[i] > max) max = arr[i];
if(arr[i] < min) min = arr[i];
}
int size = max - min + 1;
int *count =(int*)malloc(sizeof(int)*size);
memset(count, 0, sizeof(int)*size);
for(int i = 0; i < len; i++)
count[arr[i] - min]++;//包含了自己!
for(int i = 1; i < size; i++)
count[i] += count[i - 1];
int* psort =(int*)malloc(sizeof(int)*len);
memset(psort, 0, sizeof(int)*len);
for(int i = len - 1; i >= 0; i--){
count[arr[i] - min]--;//要先把自己减去
psort[count[arr[i] - min]] = arr[i];
}
for(int i = 0; i < len; i++){
arr[i] = psort[i];
}
free(count);
free(psort);
count = NULL;
psort = NULL;
}
void print_array(int *arr, int len)
{
for(int i=0; iprintf("%d ", arr[i]);
printf("\n");
}
int main()
{
int arr[8] = {2, 5, 3, 0, 2, 3, 0, 3};
CountSort(arr, 8);
print_array(arr, 8);
return 0;
}
桶式排序
简介
鸽巢排序
的一种归纳结果。当要被排序的数组内的数值是均匀分配的时候,桶排序使用线性时间(Θ(n))。但桶排序并不是 比较排序,他不受到 O(n log n) 下限的影响。复杂度与稳定性
过程介绍
根据待排序集合中最大元素和最小元素的差值范围和映射规则,确定申请的桶个数; 遍历待排序集合,将每一个元素移动到对应的桶中; 对每一个桶中元素进行排序,并移动到已排序集合中。
图示过程
代码实现
#include
#include
#include
using namespace std;
const int BUCKET_NUM = 10;
struct ListNode{
explicit ListNode(int i=0):mData(i),mNext(NULL){}
ListNode* mNext;
int mData;
};
ListNode* insert(ListNode* head,int val){
ListNode dummyNode;
ListNode *newNode = new ListNode(val);
ListNode *pre,*curr;
dummyNode.mNext = head;
pre = &dummyNode;
curr = head;
while(NULL!=curr && curr->mData<=val){
pre = curr;
curr = curr->mNext;
}
newNode->mNext = curr;
pre->mNext = newNode;
return dummyNode.mNext;
}
ListNode* Merge(ListNode *head1,ListNode *head2){
ListNode dummyNode;
ListNode *dummy = &dummyNode;
while(NULL!=head1 && NULL!=head2){
if(head1->mData <= head2->mData){
dummy->mNext = head1;
head1 = head1->mNext;
}else{
dummy->mNext = head2;
head2 = head2->mNext;
}
dummy = dummy->mNext;
}
if(NULL!=head1) dummy->mNext = head1;
if(NULL!=head2) dummy->mNext = head2;
return dummyNode.mNext;
}
void BucketSort(int n,int arr[]){
vectorbuckets(BUCKET_NUM,(ListNode*)(0));
for(int i=0;iint index = arr[i]/BUCKET_NUM;
ListNode *head = buckets.at(index);
buckets.at(index) = insert(head,arr[i]);
}
ListNode *head = buckets.at(0);
for(int i=1;ihead = Merge(head,buckets.at(i));
}
for(int i=0;iarr[i] = head->mData;
head = head->mNext;
}
}
基数排序
简介
复杂度与稳定性
图示过程
R {50, 123, 543, 187, 49, 30, 0, 2, 11, 100}
。过程介绍
我们先根据序列的个位数的数字来进行分类,将其分到指定的桶中。 分类后,我们在从各个桶中,将这些数按照从编号0到编号9的顺序依次将所有数取出来。 得到的序列就是个位数上呈递增趋势的序列。 按照上图个位数排序: {50, 30, 0, 100, 11, 2, 123, 543, 187, 49}
。接下来对十位数、百位数也按照这种方法进行排序,最后就能得到排序完成的序列。
主要代码实现
public class RadixSort {
// 获取x这个数的d位数上的数字
// 比如获取123的1位数,结果返回3
public int getDigit(int x, int d) {
int a[] = {1, 1, 10, 100}; // 本实例中的最大数是百位数,所以只要到100就可以了
return ((x / a[d]) % 10);
}
public void radixSort(int[] list, int begin, int end, int digit) {
final int radix = 10; // 基数
int i = 0, j = 0;
int[] count = new int[radix]; // 存放各个桶的数据统计个数
int[] bucket = new int[end - begin + 1];
// 按照从低位到高位的顺序执行排序过程
for (int d = 1; d <= digit; d++) {
// 置空各个桶的数据统计
for (i = 0; i < radix; i++) {
count[i] = 0;
}
// 统计各个桶将要装入的数据个数
for (i = begin; i <= end; i++) {
j = getDigit(list[i], d);
count[j]++;
}
// count[i]表示第i个桶的右边界索引
for (i = 1; i < radix; i++) {
count[i] = count[i] + count[i - 1];
}
// 将数据依次装入桶中
// 这里要从右向左扫描,保证排序稳定性
for (i = end; i >= begin; i--) {
j = getDigit(list[i], d);
// 求出关键码的第k位的数字, 例如:576的第3位是5
bucket[count[j] - 1] = list[i];
// 放入对应的桶中,count[j]-1是第j个桶的右边界索引
count[j]--; // 对应桶的装入数据索引减一
}
// 将已分配好的桶中数据再倒出来,此时已是对应当前位数有序的表
for (i = begin, j = 0; i <= end; i++, j++) {
list[i] = bucket[j];
}
}
}
public int[] sort(int[] list) {
radixSort(list, 0, list.length - 1, 3);
return list;
}
// 打印完整序列
public void printAll(int[] list) {
for (int value : list) {
System.out.print(value + "\t");
}
System.out.println();
}
public static void main(String[] args) {
int[] array = {50, 123, 543, 187, 49, 30, 0, 2, 11, 100};
RadixSort radix = new RadixSort();
System.out.print("排序前:\t\t");
radix.printAll(array);
radix.sort(array);
System.out.print("排序后:\t\t");
radix.printAll(array);
}
}
总结
有道无术,术可成;有术无道,止于术
欢迎大家关注Java之道公众号
好文章,我在看❤️
评论