本文共 1790 字,大约阅读时间需要 5 分钟。
算法思想:逐步将记录插入到已排好序的有序表中。
//直接插入排序void InsertSort(int a[], int n){ int i,j; int t; //交换中间变量 //从第二个开始插入 for(i = 2; i<=n; i++) //控制循环多少趟 { if(a[i-1]>a[i]) { a[0] = a[i]; for(j = i-1; a[j] > a[0]; j--) a[j+1] = a[j]; //大于a[0]的记录往后移 a[j+1] = a[0]; } }}
//折半插入排序 void BInsertSort(int a[], int n){ int i,j; int t; int low, high, mid; for(i = 2; i<=n; i++) //控制循环的趟数,每一趟采用折半查找 { a[0] = a[i]; low = 1; high = i-1; while(low <= high) { mid = (low + high)/2; if(a[mid] >= a[0]) high = mid - 1; else low = mid + 1; } for(j = i-1; j >= high+1; j--) //查找之后进行记录后移 a[j+1] = a[j]; a[high+1] = a[0]; }}
算法思想:从前向后依次检查每一对相邻元素,一旦发现逆序即交换二者的位置。对于长度为n的序列,共需做n - 1次比较和不超过n - 1次交换,这一过程称作一趟扫描交换。每一趟扫描都至少会有一个元素就位。
//起泡排序void BubSort(int a[], int n){ int i, j, t; for(i = 1; ia[j+1]) { t = a[j]; a[j] = a[j+1]; a[j+1] = t; } } }}
算法思想: 通过一趟排序将第一个记录排好位置,同时将待排序记录分割成独立的两部分。其中前部分的关键字都比后部分的关键字小。然后再分别对这两部分继续递归排序,以达到整个序列有序。
//第一趟排序int Partition(int a[], int low, int high){ int pkey; pkey = a[low]; while(low < high) { while(a[high] >= pkey && low < high) high--; a[low] = a[high]; while(a[low] < pkey && low < high) low++; a[high] = a[low]; } a[low] = pkey; return low;}//进行递归排序void QSort(int a[], int low, int high){ if(low < high) { int mid = Partition(a, low, high); QSort(a, low, mid-1); QSort(a, mid+1, high); }}void QuickSort(int a[], int n){ QSort(a, 1, n);}
算法思想:
void SelectSort(int a[], int n){ int i, j; int min, t; for(i = 1; i
转载地址:http://vytpz.baihongyu.com/