vlambda博客
学习文章列表

/********************选择排序********************///每次选择无序区中最小的元素与无序区中的首元素交换//交换后有序区长度加一，无序区长度减一/********************冒泡排序********************/void SelectSort(int a[], int len) {
 for (int i = 0; i < len; i++) { for (int j = i+1; j < len ; j++) { int temp = 0; if (a[i] > a[j]) { temp = a[i]; a[i] = a[j]; a[j] = temp; } } }}

void Insertsort(int a[], int len) { for (int i = 1; i < len; i++) { int temp = a[i]; int pos = i; for (int j = i - 1; j >= 0 && a[j] > temp; j--) { a[j + 1] = a[j]; pos = j; } a[pos] = temp; }}

void ShellSort(int a[], int len) { const int sublen = 2; int InsertNum = 0; unsigned gap = len / sublen; while(gap) { for (int i = gap; i < len; i++) { InsertNum = a[i]; int j = i; while (j >= gap && a[j - gap] > InsertNum) { a[i] = a[j - gap]; j -= gap; } a[j] = InsertNum; } gap = gap / sublen; }}

void Merge(int a[], int low, int mid, int high) { int n = high - low + 1;//临时数组存合并后的有序序列 int* tmp = new int[n]; int i = 0; int left = low; int right = mid + 1; while (left <= mid && right <= high) tmp[i++] = a[left] <= a[right] ? a[left++] : a[right++]; while (left <= mid) tmp[i++] = a[left++]; while (right <= high) tmp[i++] = a[right++];
 //将融合后的数据拷贝到原来的数据对应的子空间中 i = 0; while(low <= high) a[low++] = tmp[i++];
 delete[] tmp;//删掉堆区的内存}void MergeSort(int a[], int low, int high) { if (low == high) return; //递归基是让数组中的每个数单独成为长度为1的区间 int mid = (low + high) / 2; MergeSort(a, low, mid); MergeSort(a, mid+1, high); Merge(a, low, mid, high);}

int partition(int a[], int low, int high) { int pivot = a[high]; int i = low; for (int j = i; j < high; j++) { if (a[j] < pivot) { swap(a[j], a[i]); i++; } } swap(a[high], a[i]); return i;}void QuickSort(int a[], int low, int high) { if (low < high) { int q = partition(a, low, high); QuickSort(a, low, q - 1); QuickSort(a, q + 1, high); }}

/********************堆排序********************/// 最大堆 树根节点元素最大，每次将树根节点元素取出 即取到了序列最大元素// 将最大元素去掉后的剩余序列构成最大堆，不断取出最大堆的树根节点// 直到最大堆最后剩两个节点，排序完毕// 堆是完全二叉树，从下向上构建最大堆/**********************End***********************/void heapSort(int a[], int n, int len);void maxHeap(int a[], int n, int len);void buildMaxHeap(int a[], int n, int len);
void heapSort(int a[], int n, int len){ buildMaxHeap(a, n, len); for (int i = len; i > 1; i--) { swap(a[0], a[i - 1]); len = len - 1; maxHeap(a, 1, len); }}void buildMaxHeap(int a[], int n, int len){ int i = n / 2; for (i; i > 0; i--) maxHeap(a, i, len);}void maxHeap(int a[], int n, int len){ int leftChild, rightChild, largest; leftChild = 2 * n; rightChild = 2 * n + 1; if (leftChild <= len && a[leftChild - 1] > a[n - 1]) largest = leftChild; else largest = n; if (rightChild <= len && a[rightChild - 1] > a[largest - 1]) largest = rightChild; if (largest != n) { swap(a[n - 1], a[largest - 1]); maxHeap(a, largest, len); }}

/********************计数排序********************/// 需要得到序列中的数据分布范围，即序列的最大值和最小值// 要求待排序序列必须是非负整数// 在新开辟空间中记录原始序列中每个值出现的次数// 之后再根据新开辟空间中对应索引存储值的个数来返回有序序列/**********************End***********************/void CountSort(int a[], int len) {
 int temp[100] = { 0 }; int n = 0; int sortIndex = 0; for (int i = 0; i < len; i++) { temp[a[i]]++; } for (int i = 0; i < 100; i++) { while (temp[i] > 0) { a[sortIndex++] = i; temp[i]--; } }}

/********************桶排序**********************/// 首先得到待排序序列的最大最小值// 根据给定桶的容量 来确定桶的个数// 将待排序序列分别放入不同的桶中// 对于不同的桶 利用以上任意一种排序算法排序// 将桶中的数据按照桶的顺序进行整体连接排序// 本次选用计数排序对 桶中的序列排序/**********************End***********************/
void CountSort_vct(vector<int>& a) { int temp[100] = { 0 }; int n = 0; int sortIndex = 0; for (int i = 0; i < a.size(); i++) { temp[a[i]]++; } for (int i = 0; i < 100; i++) { while (temp[i] > 0) { a[sortIndex++] = i; temp[i]--; } }}void bucketSort(vector<int>& arr, int bucketSize = 10) { if (arr.size() == 0) { return; } int i; int minValue = arr[0]; int maxValue = arr[0]; for (i = 1; i < arr.size(); i++) { if (arr[i] < minValue) { minValue = arr[i]; // 待排序序列最小值 } else if (arr[i] > maxValue) { maxValue = arr[i]; // 待排序序列最大值 } } int bucketCount = int((maxValue - minValue) / bucketSize) + 1; //根据最大最小值计算桶的个数
 vector<vector<int>> buckets(bucketCount, vector<int>()); // 利用映射函数将数据分配到各个桶中  for (i = 0; i < arr.size(); i++) { int idx = int((arr[i] - minValue) / bucketSize); buckets[idx].push_back(arr[i]); } arr.clear(); for (i = 0; i < buckets.size(); i++) { CountSort_vct(buckets[i]); // 对每个桶进行排序，这里使用了计数排序，可以用上面的任意一种排序代替 for (int j = 0; j < buckets[i].size(); j++) { arr.push_back(buckets[i][j]); } } return;}