- .冒泡排序
- .选择排序
- .插入排序
- .希尔排序
- .快速排序
- .归并排序-递归
- .归并排序-循环
- .堆排序
- .桶排序
.冒泡排序
#include.选择排序using namespace std; //输出数组 void PrintArray(int a[],int length) { for (int i = 0; i < length; i++) { cout << a[i] << ' '; } cout << endl; } //冒泡排序--平均时间复杂度数O(n2),空间复杂度O(1) //适用的情景为数据量量不大，对稳定性有要求，且数据基本有序的情况下 void BubbleSort(int a[], int length) { cout << "排序前" << endl; PrintArray(a,length); bool YNchange; //是否发生了交换 for (int i = 0; i < length - 1; i++) { YNchange = false; for (int j = 0; j < length-1-i; j++) { if (a[j] > a[j + 1]) { int temp = a[j]; a[j] = a[j+1]; a[j + 1] = temp; YNchange = true; } } if (YNchange == false) break; } cout << "排序后" << endl; PrintArray(a, length); } int main() { int a[15] = {15,1,0,6,8,4,5,3,2,7,10,9,8,8,18}; BubbleSort(a,15); }
#include.插入排序using namespace std; //输出数组 void PrintArray(int a[],int length) { for (int i = 0; i < length; i++) { cout << a[i] << ' '; } cout << endl; } //选择排序-平均时间复杂度：O(n2),空间复杂度O(1) void SelctionSort(int a[], int length) { cout << "排序前" << endl; PrintArray(a, length); //在长度为N的无序数组中，第一次遍历n-1个数，找到最小的数值与第一个元素交换 for (int i = 0; i < length - 1; i++) { int Mintemp=i;//记录最小值的下标 for (int j = i + 1; j < length; j++) { if (a[j] < a[Mintemp]) { Mintemp = j; } } if (Mintemp != i) { int temp = a[i]; a[i] = a[Mintemp]; a[Mintemp] = temp; } } cout << "排序后" << endl; PrintArray(a, length); } int main() { int a[15] = {15,1,0,6,8,4,5,3,2,7,10,9,8,8,18}; SelctionSort(a, 15); }
#include.希尔排序using namespace std; //输出数组 void PrintArray(int a[],int length) { for (int i = 0; i < length; i++) { cout << a[i] << ' '; } cout << endl; } //插入排序-平均时间复杂度：O(n2),空间复杂度O(1) void InsertionSort(int a[], int length) { cout << "排序前" << endl; PrintArray(a, length); bool YNchange; for (int i = 1; i < length; i++) { for (int j = i; j >= 1; j--) { YNchange = false; if (a[j] < a[j - 1]) { int temp = a[j]; a[j] = a[j - 1]; a[j - 1] = temp; YNchange = true; } if (!YNchange) break; } } cout << "排序后" << endl; PrintArray(a, length); }
#include.快速排序using namespace std; //输出数组 void PrintArray(int a[],int length) { for (int i = 0; i < length; i++) { cout << a[i] << ' '; } cout << endl; } //希尔排序 void groupsort(int a[],int length,int ipos,int istep) { int itemp; //当前需要排序的元素的值 int ii; //需要排序元素的计数器 int jj; //插入排序时，需要后移的元素计数器 for (ii = ipos + istep; ii < length; ii += istep) { itemp = a[ii]; for (jj = ii - istep; jj >= 0; jj -= istep) { if (a[jj] <= itemp) break; a[jj + istep] = a[jj]; } a[jj + istep] = itemp; } } void shellsort(int a[],int length) { cout << "排序前" << endl; PrintArray(a, length); int ii, istep; //分别为组号(起始位置)和步长 for (istep = length / 2; istep > 0; istep /= 2) { for (ii = 0; ii < istep; ii++) { groupsort(a,length,ii,istep); } } cout << "排序后" << endl; PrintArray(a, length); }
#include.归并排序-递归using namespace std; //输出数组 void PrintArray(int a[],int length) { for (int i = 0; i < length; i++) { cout << a[i] << ' '; } cout << endl; } //快速排序 void quicksort(int *a, int length) { if (length < 2)return; int itemp = a[0]; //选择最左边的数作为中心轴 int ileft = 0; //左下标 int iright = length - 1; //右下标 int imoving = 2; //当前应该移动的下标 1- 2- while (ileft < iright) { if (imoving == 2) { //大于中心轴继续移动 if (a[iright] >= itemp) { iright--; continue; } //小于中心轴，把放在左下标的位置 a[ileft] = a[iright]; ileft++; imoving = 1; continue; } if (imoving == 1) { //小于中心轴继续移动 if (a[iright] <= itemp) { ileft++; continue; } //大于中心轴，把放在左下标的位置 a[iright] = a[ileft]; iright--; imoving = 2; continue; } } a[ileft] = itemp; quicksort(a, ileft); quicksort(a + ileft+1, length - ileft-1); }
#include.归并排序-循环using namespace std; //输出数组 void PrintArray(int a[],int length) { for (int i = 0; i < length; i++) { cout << a[i] << ' '; } cout << endl; } //归并排序-递归 void memcpy(int* arr, int* arrtmp,int length) { for (int i = 0; i < length; i++) { arr[i] = arrtmp[i]; } } void _mergesort(int* arr, int* arrtmp, int start, int end) { //如果区间元素少于两个，递归终止 if (start >= end) return; int mid = start+(end-start) / 2; int istart1 = start, iend1 = mid; int istart2 = mid + 1, iend2 = end; _mergesort(arr, arrtmp, istart1, iend1); _mergesort(arr, arrtmp, istart2, iend2); int ii = start; while (istart1 <= iend1 && istart2 <= iend2) arrtmp[ii++] = arr[istart1] < arr[istart2] ? arr[istart1++] : arr[istart2++]; while (istart1 <= iend1) arrtmp[ii++] = arr[istart1++]; while (istart2 <= iend2) arrtmp[ii++] = arr[istart2++]; memcpy(arr+start,arrtmp+start,end-start+1); } void mergesort(int a[],int length) { cout << "排序前" << endl; PrintArray(a, 15); if (length < 2) return; int *arrtemp = new int[length]; _mergesort(a, arrtemp,0,length-1); cout << "排序后" << endl; PrintArray(a, 15); }
#include.堆排序using namespace std; //输出数组 void PrintArray(int a[],int length) { for (int i = 0; i < length; i++) { cout << a[i] << ' '; } cout << endl; } //归并排序-循环 void Mergesort(int a[], int length) { cout << "排序前" << endl; PrintArray(a, 15); if (length < 2) return; int *aa = a; //指向排序数组 int* bb = new int[length];//指向已排序的数组 int iseg;//区分分端的计数器 int istart;//区间起始位置的计数器 for (iseg = 1; iseg < length; iseg *= 2) { //处理每个区间 for (istart = 0; istart < length; istart = istart + iseg * 2) { int ilow = istart; int imid = min(istart+iseg,length); int imax = min(istart+iseg*2,length); int ii = ilow; int istart1 = ilow, iend1 = imid; int istart2 = imid, iend2 = imax; //将待排序的左右数列合并 while ((istart1 < iend1) && (istart2 < iend2)) bb[ii++] = aa[istart1] < aa[istart2] ? aa[istart1++] : aa[istart2++]; while (istart1 < iend1) bb[ii++] = aa[istart1++]; while (istart2 < iend2) bb[ii++] = aa[istart2++]; } //交换数组指针，准备下一次排序 int* ptem = aa; aa = bb; bb = ptem; } cout << "排序后" << endl; PrintArray(a, 15); }
#include.桶排序using namespace std; //输出数组 void PrintArray(int a[],int length) { for (int i = 0; i < length; i++) { cout << a[i] << ' '; } cout << endl; } //堆排序 void heapify(int* arr,int start,int end) { int dad = start; int son = dad * 2 + 1; while (son<=end) { if ((son + 1 <= end) && (arr[son] < arr[son + 1])) son++; if (arr[dad] > arr[son]) return; swap(arr[dad],arr[son]); dad = son; son = dad * 2 + 1; } } void heapsort(int* arr, int len) { cout << "排序前" << endl; PrintArray(arr, 15); int ii; //初始化堆 for (ii =(len-2)/2;ii>=0;ii--) { heapify(arr,ii,len-1); } //把最后一个元素和堆的最后一个元素交换，然后重新调整 for (ii = len - 1; ii > 0; ii--) { swap(arr[0],arr[ii]); heapify(arr, 0, ii- 1); } cout << "排序后" << endl; PrintArray(arr, 15); }
#includeusing namespace std; //输出数组 void PrintArray(int a[],int length) { for (int i = 0; i < length; i++) { cout << a[i] << ' '; } cout << endl; } //桶排序 void _BubbleSort(int a[], int length) { bool YNchange; //是否发生了交换 for (int i = 0; i < length - 1; i++) { YNchange = false; for (int j = 0; j < length - 1 - i; j++) { if (a[j] > a[j + 1]) { int temp = a[j]; a[j] = a[j + 1]; a[j + 1] = temp; YNchange = true; } } if (YNchange == false) break; } } void bucketsort(int arr[],int len) { cout << "排序前" << endl; PrintArray(arr, 15); //分配一个bucker[5][20]数组,5个桶 int** bucket; bucket = new int* [5]; for (int i = 0; i < 5; i++) { bucket[i] = new int[20]; } //每个桶元素个数的计算器 int* bucketsize = new int[5]{0}; //按0-9,...41-49的规则放入桶 for (int ii = 0; ii < len; ii++) { int index = arr[ii] / 10; bucket[index][bucketsize[index]] = arr[ii]; bucketsize[index] += 1; } //对每个桶进行冒泡排序 for (int ii = 0; ii < 5; ii++) { _BubbleSort(bucket[ii], bucketsize[ii]); } //将每个桶里的内容组合赋值给arr int jj = 0; for (int ii = 0; ii < 5; ii++) { for (int ij = 0; ij < bucketsize[ii]; ij++) arr[jj++] = bucket[ii][ij]; } cout << "排序后" << endl; PrintArray(arr, 15); }
