排序算法

2019-11-06 07:12:55

字体：大中小

来源：转载

供稿：网友

冒泡排序

？有疑问，基本冒泡排序1

#include<stdio.h>void bubble_sort1(int array[],int arraySize){ int i,j,tmp; for(i=0;i<arraySize-1;i++)/*每次在末尾排好一个，循环n-1次*/ { for(j=0;j<arraySize-1-i;j++)/*遍历*/ { if(array[j]>array[j+1])/*交换*/ { /*tmp=array[j]; array[j]=array[j+1]; array[j+1]=tmp;*/ array[j]^=array[j+1]^=array[j]^=array[j+1]; } } }}int main(void){ int array[5]={2,1,3,5,4}; bubble_sort1(array,5);/*排序好后为：1 2 3 4 5*/ int i; for(i=0;i<5;i++)PRintf("%d",array[i]); puts("");}

以前做排序为了省事直接在创建在*.cpp里，今天遇到问题了。这段代码在g++下运行正确,输出为12345 但在gcc下运行错误，输出为00235。应该错在这句话：array[j]^=array[j+1]^=array[j]^=array[j+1]; 疑问：不知两种编译下，是异或运算有区别？还是gcc有特殊的序列点？不了解其中本质。 一个数（同一个地址）自己与自己异或3次会是0，但下角标是j和j+1，应该不会涉及到这种情况。

这里写图片描述

选择排序

普通选择排序

#include<stdio.h>void selectionSort(int array[],int arraySize){ for(int i=0; i<arraySize-1; i++) { int MIN=i; for(int j=i+1; j<arraySize; j++)array[j]<array[MIN]?MIN=j:0; if(MIN!=i) array[MIN]^=array[i]^=array[MIN]^=array[i]; }}int main(){ int array[5]= {3,2,4,5,1}; selectionSort(array,5); for (int i = 0; i < 5; i++)printf("%d ", array[i]);}

插入排序

普通插入排序

#include<stdio.h>void insertionSort1(int array[],int arraySize){//无哨兵 int temp; for(int i=1;i<arraySize;i++) { int j=i-1; //将大于temp的值向后移一个单位 for(temp=array[i];j>=0&&temp<array[j];j--)array[j+1]=array[j]; //腾出temp应该在的那个位置，并插入 array[j+1]=temp; } }void insertionSort2(int array[],int arraySize){//a[0]是哨兵 for(int i=2;i<arraySize;i++) { int j=i-1; //a[0]起到temp的作用，而且也不用判断j>=0 for(array[0]=array[i];array[0]<array[j]; j--) array[j+1]=array[j]; array[j+1]=array[0]; }}int main(void){ int a[5]= {4,1,3,5,2}; insertionSort1(a,5); for(int i=0; i<5; i++)printf("%d ",a[i]); puts(""); int b[6]= {0,4,1,3,5,2};/*第一个数0，是哨兵*/ insertionSort2(b,6); for(int i=1; i<6; i++)printf("%d ",b[i]); puts("");}

折半排序法（二分插入排序法）

#include<stdio.h>void halfsort(int array[],int arraySize){ int i,j,temp,low,mid,high; //最初的第一个元素想象成已经排好的序列 //遍历后面的元素，将其插入到已排序好的序列中 for(i=1;i<arraySize;i++) { low=0;//已经排序号的序列的最低位置 high=i-1;//已经排序号的序列的最高位置 temp=array[i];//每次将array[i]插入到以排序的序列中 while(low<=high)//二分查找 { mid=(low+high)/2; if(array[mid]>temp)high=mid-1; else low=mid+1; } //找到插入点后，为该值腾出地方，将high+1到i的所有元素后移一位 for(j=i-1;j>high;j--)array[j+1]=array[j]; array[high+1]=temp; }}int main(){ int array[5]={3,2,5,4,1},i; halfSort(array,5); for(i=0; i<5; i++)printf("%d ",array[i]);}

希尔排序

很久以前从网上扒下来的

#include<stdio.h>#include<math.h>void shellInsert(int array[],int n,int dk)///根据当前增量dk进行插入排序{ int i,j,temp; for(i=dk; i<n; i++) //分别向每组的有序区域插入 { temp=array[i]; for(j=i-dk; (j>=i%dk)&&array[j]>temp; j-=dk) //比较与记录后移同时进行 array[j+dk]=array[j]; if(j!=i-dk) array[j+dk]=temp;//插入 }}void shellSort(int array[],int n,int t)///希尔排序{ int dk = n/2; while( dk >= 1 ){ shellInsert(array, n, dk); dk = dk/2; }}int main(){ int array[100],i,n; scanf("%d",&n); for(i=0; i<n; i++) scanf("%d",&array[i]); shellSort(array,n,int(log(n+1)/log(2)));//排序趟数应为log2(n+1)的整数部分 for(i=0; i<n; i++) printf("%d ",array[i]); printf("/n");}

地精排序

一个循环…但是变量i跑的太折腾了…

#include<stdio.h>void gnomesort(int array[],int arraySize){ int i=0; while(i<arraySize) { if(i==0||array[i-1]<=array[i])i++; else { int tmp = array[i]; array[i] = array[i-1]; array[--i] = tmp; } }}int main(){ int array[5]= {4,3,1,5,2}; gnomesort(array,5);/*排序后结果为1 2 3 4 5*/ for(int i=0; i<5; i++)printf("%d ",array[i]);}

快速排序

递归快速排序

#include <stdio.h>void QuickSort(int array[], int left, int right){ int i = left,j = right; int temp = array[i]; if( left < right) { while(i < j) { while(array[j] >= temp && i < j)j--; array[i] = array[j]; while(array[i] <= temp && i < j)i++; array[j] = array[i]; } array[i] = temp; QuickSort(array, left, i - 1); QuickSort(array, j + 1, right); }}int main(){ int array[5] = {3,2,4,5,1},i; QuickSort(array, 0, 4); for (i = 0; i < 5; i++)printf("%d ",array[i]);}

计数排序

普通计数排序

计数排序是一个非基于比较的排序算法

#include <stdio.h>#include <string.h>#define MAXNUM 1000//排序的数字范围是0-1000void countingSort(int A[], int n, int k){ int temp[k], out[n],i; memset(temp,0,sizeof(temp)); for (i = 0; i < n; i++) temp[A[i]]++; for (i = 1; i < k; i++) temp[i] += temp[i-1]; for (i = n - 1; i >= 0; i--) out[--temp[A[i]]] = A[i]; memcpy(A,out,sizeof(out));}int main(){ int A[5]= {3,1,5,4,2},i; countingSort(A, 5, MAXNUM); for (i = 0; i < 5; i++)printf("%d ", A[i]);}

上一篇：访问权限控制

下一篇：编程技巧,数组覆盖