面试常考排序算法

//直接插入排序void InsertSort(int A[], int n){int i,j;int temp;for (i=0;i<n-1;i++){temp=A[i+1];j=i;while (j>-1&&temp<A[j]){A[j+1]=A[j];j--;}A[j+1]=temp;}}//冒泡排序void BubbleSort(int A[],int n){int i, j, flag=1;int temp;for (i=1;i<n&&flag;i++){flag=0;for (j=0;j<n-i;j++){if(A[j+1]<A[j]){flag=1;temp=A[j+1];A[j+1]=A[j];A[j]=temp;}}}}

//快速排序void QuickSort(int A[], int left, int right){int i=left, j=right;int temp=A[left];while(i<j){while(i<j&&temp<=A[j])j--;if(i<j)A[i++]=A[j];while(i<j&&A[i]<temp)i++;if(i<j)A[j--]=A[i];}A[i]=temp;if(left<i)QuickSort(A,left,i-1);if(j<right)QuickSort(A,j+1,right);}

//快速排序（划分）

int Partition(int A[], int n, int start, int end){if(A==NULL||n<=0||start<0||end>=n)return -1;int index=RandomInRange(start, end);swap(&A[index],&A[end]);int small=start-1;for (index=start; index<end; ++index){if(A[index]<A[end]){small++;if(index!=small){swap(&A[small],&A[index]);}}}small++;swap(&A[small],&A[end]);return small;}void QuickSort(int A[], int n, int left, int right){if(left==right)return;int index=Partition(A, n, left, right);if(index>left)QuickSort(A,n,left,index-1);if(index<right)QuickSort(A,n,index+1,right);}void getLeastKnum(int A[], int n, int B[], int k){if(A==NULL||n<=0||B==NULL||k<=0||n<k)return;int start=0;int end=n-1;int index=Partition(A,n,start,end);while(index!=k-1){if(index>k-1)index=Partition(A,n,start,index-1);elseindex=Partition(A,n,index+1,end);}for (int i=0;i<k;i++)B[i]=A[i];}

如果觉得《面试常考排序算法》对你有帮助，请点赞、收藏，并留下你的观点哦！