whtqsq 2019-06-21
void bubbleSort(vector<int>&); void buidHeap(vector<int>&); void heapSort(vector<int>&); void qsort(int, int, vector<int>&); void quickSort(vector<int>&); int quickSelect(int,int, int , int[]); void mSort(int, int, vector<int>&, vector<int>&); void mergeSort(vector<int>&);
void qsort(int low , int high, vector<int>& vec){ if (low >= high) return; // optimization int idx = low + random() % (high - low + 1); swap(vec[low], vec[idx]); int pivot = vec[low]; int l = low; int h = high; while (low < high){ while (low < high && vec[high] >= pivot){ high--; } vec[low] = vec[high]; while (low < high && vec[low] <= pivot){ low++; } vec[high] = vec[low]; } vec[low] = pivot; qsort(l, low - 1, vec); qsort(low + 1, h, vec); } void quickSort(vector<int>& vec){ qsort(0, static_cast<int>(vec.size()) - 1, vec); }
int quickSelect(int k ,int low, int high, int vec[]){ int pivot = low + rand() % (high - low + 1); swap(vec[low], vec[pivot]); int val = vec[low]; int l = low, h = high; while (low < high){ while (low < high && vec[high] >= val){ high--; } vec[low] = vec[high]; while (low < high && vec[low] <= val){ low++; } vec[high] = vec[low]; } vec[low] = val; if (low == k){ return vec[low]; } else if (low > k ){ return quickSelect(k, l, low - 1, vec); } else{ return quickSelect(k, low + 1, h, vec); } }
void bubbleSort(vector<int>& vec){ for (int i = 0; i < static_cast<int>(vec.size()) - 1; ++i){ bool isSorted = true; for (int j = static_cast<int>(vec.size()) - 1; j > i; --j){ if (vec[j - 1] > vec[j]){ swap(vec[j - 1], vec[j]); isSorted = false; } } if (isSorted == true) break; } }
void buildHeap(vector<int>& heap){ int len = static_cast<int>(heap.size()); for (int i = len / 2; i > 0; --i){ int j = i; while (j * 2 <= len) { int child = j * 2; if (child + 1 <= len && heap[child] > heap[child - 1]){ child++; } if (heap[j - 1] < heap[child - 1]){ swap(heap[j - 1], heap[child - 1]); j = child; } else{ break; } } } }
void heapSort(vector<int>& heap){ buildHeap(heap); int len = static_cast<int>(heap.size()); for (int i = len; i >= 1; --i){ int j = 1; swap(heap[j - 1], heap[i - 1]); while (j * 2 <= i - 1) { int child = j * 2; if (child + 1 <= i - 1 && heap[child] > heap[child - 1]){ child++; } if (heap[j - 1] < heap[child - 1]){ swap(heap[j - 1], heap[child - 1]); j = child; } else{ break; } } } }
void mSort(int low, int high, vector<int>& vec, vector<int>& backup){ if (low >= high) return; int mid = low + (high - low) / 2; mSort(low, mid, vec, backup); mSort(mid + 1, high, vec, backup); for (int i = low, j = mid + 1, k = low; i <= mid || j <= high; ++k){ if (j > high || ( i <= mid && vec[i] <= vec[j]) ){ backup[k] = vec[i++]; } else{ backup[k] = vec[j++]; } } for (int i = low; i <= high; ++i){ vec[i] = backup[i]; } } void mergeSort(vector<int>& vec){ vector<int> backup(vec.size(), 0); mSort(0, static_cast<int>(vec.size()) - 1, vec, backup); }