Các Giải Thuật Sắp Xếp - Sorting Algorithms

Tổng hợp các giải thuật sắp xếp với ngôn ngữ lập trình C++.

Hàm đổi giá trị 2 số - swap

12345678910
void swap(int & a, int & b) { int temp = a; a = b; b = temp; } void printArray(int arr[], int numberOfElemens) { for (int i = 0; i < numberOfElements; i++) cout << arr[i] << " "; }

Sắp xếp nổi bọt - Bubble sort

12345678910111213141516
void bubbleSort(int arr[], int numberOfElements) { for (int i = 0; i < numberOfElements - 1; i++) for (int j = numberOfElements - 1; j > i; j--) if (arr[j] < arr[j - 1]) swap(arr[j], arr[j - 1]); } int main() { int arr[] = {2, 3, 1, -3, 5, -6, 7, 8, 6, 9}; int numberOfElements = sizeof(arr) / sizeof(arr[0]); bubbleSort(arr, numberOfElements); printArray(arr, numberOfElements); return 0; }

Sắp xếp chèn - Insertion sort

12345678910111213141516171819202122
void insertionSort(int arr[], int numberOfElements) { for (int i = 1; i < numberOfElements; i++) { int temp = arr[i]; int j = i - 1; while (temp < arr[j] && j >= 0) { arr[j + 1] = arr[j]; j--; } arr[j + 1] = temp; } } int main() { int arr[] = {2, 3, 1, -3, 5, -6, 7, 8, 6, 9}; int numberOfElements = sizeof(arr) / sizeof(arr[0]); insertionSort(arr, numberOfElements); printArray(arr, numberOfElements); return 0; }

Sắp xếp đổi chỗ trực tiếp - Interchange sort

12345678910111213141516
void interchangeSort(int arr[], int numberOfElements) { for (int i = 0; i < numberOfElements - 1; i++) for (int j = i + 1; j < numberOfElements ; j++) if (arr[i] > arr[j]) swap(arr[i], arr[j]); } int main() { int arr[] = {2, 3, 1, -3, 5, -6, 7, 8, 6, 9}; int numberOfElements = sizeof(arr) / sizeof(arr[0]); interchangeSort(arr, numberOfElements); printArray(arr, numberOfElements); return 0; }

Sắp xếp vun đống - Heap sort

123456789101112131415161718192021222324252627282930313233343536
void heapify(int arr[], int heapSize, int i) { int largest = i; int left = 2 * i + 1; int right = 2 * i + 2; if (left < heapSize && arr[left] > arr[largest]) largest = left; if (right < heapSize && arr[right] > arr[largest]) largest = right; if (largest != i) { swap(arr[i], arr[largest]); heapify(arr, heapSize, largest); } } void heapSort(int arr[], int numberOfElements) { for (int i = numberOfElements / 2 - 1; i >= 0; i--) heapify(arr, numberOfElements, i); for (int i = numberOfElements - 1; i >= 0; i--) { swap(arr[0], arr[i]); heapify(arr, i, 0); } } int main() { int arr[] = {2, 3, 1, -3, 5, -6, 7, 8, 6, 9}; int numberOfElements = sizeof(arr) / sizeof(arr[0]); heapSort(arr, numberOfElements); printArray(arr, numberOfElements); return 0; }

Sắp xếp trộn - Merge sort

1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253
void merge(int arr[], int left, int middle, int right) { int *lArr = new int[middle - left + 1]; int *rArr = new int[right - middle]; for (int i = 0; i < middle - left + 1; i++) lArr[i] = arr[left + i]; for (int i = 0; i < right - middle; i++) rArr[i] = arr[middle + 1 + i]; int i = 0, j = 0, k = left; while (i < middle - left + 1 && j < right - middle) { if (lArr[i] <= rArr[j]) { arr[k] = lArr[i]; i++; } else { arr[k] = rArr[j]; j++; } k++; } while (i < middle - left + 1) arr[k++] = lArr[i++]; while (j < right - middle) arr[k++] = rArr[j++]; delete[] lArr; delete[] rArr; } void mergeSort(int arr[], int left, int right) { if (left < right) { int middle = (left + right) / 2; mergeSort(arr, left, middle); mergeSort(arr, middle + 1, right); merge(arr, left, middle, right); } } int main() { int arr[] = {2, 3, 1, -3, 5, -6, 7, 8, 6, 9}; int numberOfElements = sizeof(arr) / sizeof(arr[0]); mergeSort(arr, 0, numberOfElements - 1); printArray(arr, numberOfElements); return 0; }

Sắp xếp chèn nhị phân - Insertion binary sort

123456789101112131415161718192021222324252627282930313233343536373839
int binarySearch(int arr[], int key, int left, int right) { if (right <= left) return key > arr[left] ? left + 1 : left; int mid = (left + right) / 2; if (key == arr[mid]) return mid + 1; if (key > arr[mid]) return binarySearch(arr, key, mid + 1, right); return binarySearch(arr, key, left, mid - 1); } void insertionBinarySort(int arr[], int numberOfElements) { for (int i = 1; i < numberOfElements; i++) { int j = i - 1; int temp = arr[i]; int position = binarySearch(arr, temp, 0, j); while (j >= position) { arr[j + 1] = arr[j]; j--; } arr[j + 1] = temp; } } int main() { int arr[] = {2, 3, 1, -3, 5, -6, 7, 8, 6, 9}; int numberOfElements = sizeof(arr) / sizeof(arr[0]); insertionBinarySort(arr, numberOfElements); printArray(arr, numberOfElements); return 0; }

Sắp xếp nhanh - Quick sort

1234567891011121314151617181920212223242526272829303132
void quickSort(int arr[], int left, int right) { int key = arr[(left + right) / 2]; int i = left, j = right; while (i < j) { while (arr[i] < key) i++; while (arr[j] > key) j--; if (i <= j) { swap(arr[i], arr[j]); i++; j--; } } if (left < j) quickSort(arr, left, j); if (i < right) quickSort(arr, i, right); } int main() { int arr[] = {2, 3, 1, -3, 5, -6, 7, 8, 6, 9}; int numberOfElements = sizeof(arr) / sizeof(arr[0]); quickSort(arr, 0, numberOfElements - 1); printArray(arr, numberOfElements); return 0; }

Sắp xếp lựa chọn - Selection sort

12345678910111213141516171819202122
void selectionSort(int arr[], int numberOfElements) { for (int i = 0; i < numberOfElements - 1; i++) { int minIndex = i; for (int j = i + 1; j < numberOfElements; j++) if (arr[j] < arr[minIndex]) minIndex = j; if (minIndex != i) swap(arr[minIndex], arr[i]); } } int main() { int arr[] = {2, 3, 1, -3, 5, -6, 7, 8, 6, 9}; int numberOfElements = sizeof(arr) / sizeof(arr[0]); selectionSort(arr, numberOfElements); printArray(arr, numberOfElements); return 0; }

Sắp xếp rung lắc - Shaker sort

123456789101112131415161718192021222324252627282930313233
void shakerSort(int arr[], int numberOfElements) { int left = 0; int right = numberOfElements - 1; int s = 0; while (left < right) { for (int i = right; i > left; i--) { if (arr[i] < arr[i - 1]) { swap(arr[i], arr[i - 1]); s = i; } } left = s; for (int j = left; j < right; j++) { if (arr[j] > arr[j + 1]) { swap(arr[j], arr[j + 1]); s = j; } } right = s; } } int main() { int arr[] = {2, 3, 1, -3, 5, -6, 7, 8, 6, 9}; int numberOfElements = sizeof(arr) / sizeof(arr[0]); shakerSort(arr, numberOfElements); printArray(arr, numberOfElements); return 0; }