#include<iostream> using namespace std; /*交换排序--冒泡排序 基本思想：在要排序的一组数中，对当前还未排序的全部数，自上而下对相邻的两个数依次进行比较和调整， 让较大的数往下沉淀，较小的数往上冒 对冒泡排序法的改进方法是加入一标志性变量exhange，用于标志某一趟排序中是否有数据交换，如果进行某一趟排序 没有进行数据交换，则说明数据已经按要求排列好了，可立即结束排序。 //设置一标志性变量pos,用于记录每趟排序中最后一次进行交换的位置。由于pos位置之后的记录均已交换到位，故 在进行下一趟排序时只要扫描到pos位置即可。 */ void print(int a[],int n,int i){ cout<<i<<endl; for(int j=0;j<n;j++){ cout<<a[j]<<" "; } cout<<endl; } void bubbleSort(int a[],int n){ int i=n-1;//设置初始时，最后位置保持不变 while(i>0){ int pos=0;//每趟开始无交换记录 for(int j=0;j<i;j++){ if(a[j]>a[j+1]){ pos=j; int tmp=a[j+1];a[j+1]=a[j];a[j]=tmp; } } i=pos; print(a,n,i); } }
#include<iostream> using namespace std; /************************************** 交换排序--快速排序 基本思想：1选择一个基准元素，通常选择第一个元素或者最后一个元素 2通过一趟排序将待排序的记录分割成独立的两部分，其中一 部分元素均比基准值小，另一部分元素的值比基准元素值大。 3此时基准元素在其排好顺序后的正确位置。 4然后分别对这两部分记录用同样的方法继续进行排序，直到 整个序列有序。 ***************************************/ void print(int a[],int n,int i){ cout<<i<<endl; for(int j=0;j<n;j++){ cout<<a[j]<<" "; } cout<<endl; } void swap(int &a,int &b){ int tmp; tmp=a; a=b; b=tmp; } /*********************************** Function:partition Describe: Call:swap print Input:int a[] 要排序的数组值 int low 数组左边值，低下标值 int high 数组右边值,高下标值 Return:low 返回基准元素的位置 ************************************/ int partition(int a[],int low,int high){ int privotKey=a[low];//基准元素的值 while(low<high){//从表两端交替向中间扫描，当low>=high时完毕 while (low<high&&privotKey<=a[high])--high; swap(a[low],a[high]); while(low<high&&privotKey>=a[low])++low; swap(a[low],a[high]); } print(a,8,1); return low; } /********************************************* Call:partition Describe:递归调用，划分数组，直到划分至数组长度为1，也就排好序列了 Input：a[] 排序数组 int low 数组的低位坐标 int high 数组的高位坐标 **********************************************/ void quickSort(int a[],int low,int high){ if(low<high){ int privotloc=partition(a,low,high);//将表一分为二 quickSort(a,low,privotloc-1); quickSort(a,privotloc+1,high); } } //对快排的改进：只对长度大于k的子序列递归调用快速排序法， // 让原序列基本有序，然后再对整个基本有序序列用插入算法 //排序。实践证明，改进后的算法时间复杂度有所降低，且k取值 //为8左右的时候，改进算法性能最佳。 int main(){ //int a[8]={3,1,5,7,2,4,9,6}; int a[4]={3,1,5,}; quickSort(a,0,2); }
#include<iostream> using namespace std; /*堆排序--初始时把要排序的n个数看做是一颗顺序存储的二叉树（一维数组存储二叉树） 调整它们的存储顺序使之成为一个堆，将堆顶元素输出，得到n个元素中最小或最大的元素， 这时堆的根节点的数最小或最大。然后对前面的n-1个元素重新调整顺序使之成为一个新堆，输出 堆顶端元素，得到n个元素中次小（或次大）元素。依次类推，输出堆顶端元素，直到只有两个节点 的堆，并对它们作交换，最后得到n个节点的有序序列。称这个过程为堆排序。 两个问题：1如何将n个待排序的数建成堆2输出堆顶元素后，怎样调整n-1个元素的位置，使之成为新堆。 */ void print(int a[],int n,int i){ cout<<i<<endl; for(int j=0;j<n;j++){ cout<<a[j]<<" "; } cout<<endl; } //堆排序的两个过程，一是建立堆，二是堆顶与堆的最后元素交换位置后，建立新堆。 //1建堆渗透函数 void heapAdjust(int h[],int s,int length){ int tmp=h[s];//s根节点位置 int child=2*s+1;//左节点位置孩子 while(child<length){ if(child+1<length&&h[child]<h[child+1]){ //如果右孩子比左孩子大，找到比当前待调整节点大的孩子节点 ++child; } if(h[s]<h[child]){ //如果较大的孩子节点大于父节点 h[s]=h[child];//把较大子节点与父节点交换位置 s=child;//重设s，即待调整节点的位置 child=2*s+1; } else{//如果当前调整的节点大于它的左右孩子则不需要调整直接退出 break; } h[s]=tmp;//当前节点放到比它大的孩子节点位置 } } //初始堆调整。将h[0...n-1]建成堆 void buildingHeap(int a[],int length){ //最后一个节点的位置i=(length-1)/2 for(int i=(length-1)/2;i>=0;i--) heapAdjust(a,i,length); } void heapSort(int h[],int length){ //初始堆 buildingHeap(h,length); //从最后一个元素开始对序列进行调整 for(int i=length-1;i>=0;i--){ int tmp=h[i];h[i]=h[0];h[0]=tmp; //每次交换堆顶元素之后都要对堆进行调整 heapAdjust(h,0,i);} print(h,8,1); } int main(){ int a[8]={3,1,5,7,2,4,9,6}; heapSort(a,8); }
// InsertSort.cpp : 定义控制台应用程序的入口点。 // #include "stdafx.h" #include<iostream> using namespace std; /*插入排序：直接插入排序，希尔排序 选择排序：简单选择排序，堆排序 交换排序：冒泡排序，快速排序 归并排序，基数排序 时间复杂度来说： 1.平方阶(O(n^2)):简单排序，直接插入，直接选择，冒泡排序 2.线性对数阶(O(nlogn)):快速排序，堆排序和归并排序 3.（O(n^1-2)）希尔排序 4.线性排序(O(n)):基数排序 */ /*直接插入排序，将一个记录插入到已排序好的有序列表中，从而得到一个新的记录数加1的有序表。 要设立哨兵，作为临时存储和判断数组边界之用。 */ template <class T> //c++中计算字符串长度用strlen();没有直接计算数组长度的函数 //定义一个模板函数，实现数组计算。 int getArrayLen(T& array) {//使用模板定义一 个函数getArrayLen,该函数将返回数组array的长度 return (sizeof(array) / sizeof(array[0])); } void print(int a[],int n,int i){ cout<<i<<endl; for(int j=0;j<n;j++){ cout<<a[j]<<" "; } cout<<endl; } //a[8]={3,1,5,7,2,4,9,6} void InsertSort(int a[],int n){ for(int i=1;i<n;i++){ if(a[i]<a[i-1]){ //若第i个数大于第i-1个数，直接插入，小于的话移动有序表后插入 int j=i-1; int x=a[i];//复制为哨兵 while(x<a[j]){//移动有序表 a[j+1]=a[j]; j--; } a[j+1]=x; }//if print(a,n,i); }//for } int _tmain(int argc, _TCHAR* argv[]) { int a[8]={3,1,5,7,2,4,9,6}; int n=getArrayLen(a); InsertSort(a,n); print(a,n,n); return 0; }