各种排序算法学习整理 C++实现

感谢网上各位大神的讲解，参考了网上多位大神的博客，做出了这次整理。

排序算法中用到的函数：

void Swap(int* a, int* b) { int tmp = *a; *a = *b; *b = tmp; } void PrintArray(int data[],int length) { for (int i = 0; i < length; i++) { cout << data[i] << " "; } cout << endl; }

1.冒泡排序

/*交换排序：冒泡排序*/ void bubbleSort(int data[], int length) { if (data == nullptr || length <= 0) return; for (int i = 0; i < length - 1; i++) { for (int j = 0; j < length - i - 1; j++) { if (data[j]>data[j + 1]) Swap(&data[j], &data[j + 1]); } } }

2.快速排序

/*交换排序：快速排序*/ int Partition(int data[], int length, int start, int end) { if (data == nullptr || length <= 0 || start < 0 || end >= length) throw new exception("invalid parameters!"); int index = start; int small = start - 1; for (index; index < end; index++) { if (data[index] < data[end]) { ++small; if (small != index) { Swap(&data[small], &data[index]); } } } ++small; Swap(&data[small], &data[end]); return small; } void QuickSort(int data[], int length, int start, int end) { if (start == end) return; int index = Partition(data, length, start, end); if (index > start) QuickSort(data, length, start, index - 1); if (index < end) QuickSort(data, length, index + 1, end); }

3.堆排序

/*选择排序：堆排序*/ void HeapAdjust(int data[], int s, int length) { int tmp = data[s]; int child = s * 2 + 1; //这是当前节点的左孩子！！！ while (child < length) { if (child + 1 < length&&data[child] < data[child + 1]) ++child; //要找到左右孩子中比较大的那个 if (data[s] < data[child]) { data[s] = data[child]; s = child; child = s * 2 + 1; } else break; data[s] = tmp; } } void BuildHeap(int data[], int length) { if (data == nullptr || length <= 0) return; for (int i = (length - 1) / 2; i >= 0; i--) //初始建堆是从下往上 { HeapAdjust(data, i, length); } } void HeapSort(int data[], int length) { BuildHeap(data, length); for (int i = length - 1; i > 0; --i) { Swap(&data[0], &data[i]); HeapAdjust(data, 0, i); } }

4.简单选择排序

/*选择排序：简单选择排序*/ void SelectSort(int data[], int length) { if (data == nullptr || length <= 0) return; for (int i = 0; i < length - 1; i++) { int min = i; for (int j = i+1; j < length; j++) { if (data[min]>data[j]) { min = j; } } Swap(&data[min], &data[i]); } }

5.直接插入排序

/*插入排序：直接插入排序*/ void InsertSort(int data[], int length) { for (int i = 1; i < length; i++) { if (data[i] < data[i - 1]) { int tmp = data[i]; int j = i-1; while (j >= 0 && data[j]>tmp) { data[j+1] = data[j]; j -= 1; } data[j + 1] = tmp; } } }

6.希尔排序

/*插入排序：希尔排序*/ void ShellSort(int data[], int length) { int i, j, gap; for (gap = length / 2; gap > 0; gap /= 2) { for (i = 0; i < gap; i++) { //直接插入排序 for (j = i + gap; j < length; j += gap) { if (data[j] < data[j - gap]) { int tmp = data[j]; int k = j - gap; while (k >= 0 && data[k]>tmp) { data[k + gap] = data[k]; k -= gap; } data[k + gap] = tmp; } } } } }

7.归并排序

/*归并排序*/ void MergeArray(int data[], int start, int mid, int end) { vector<int> tmp; int another_start = mid + 1; int i = start; int j = another_start; while (i <= mid&&j <= end) { if (data[i] < data[j]) { tmp.push_back(data[i++]); } else { tmp.push_back(data[j++]); } } while (i <= mid) { tmp.push_back(data[i++]); } while (j <= end) { tmp.push_back(data[j++]); } for (unsigned int i = 0; i < tmp.size(); i++) { data[start + i] = tmp[i]; } } void MergeSort(int data[], int start, int end) { if (data == nullptr || start < 0) throw new exception("invalid parameters!"); if (start < end) { int mid = (start + end) / 2; MergeSort(data, start, mid); MergeSort(data, mid + 1, end); MergeArray(data, start, mid, end); } }

测试

#include <iostream> #include <stdlib.h> #include <vector> using namespace std; int main() { //int data[] = { 49, 38, 65, 97, 76, 13, 27, 49 }; int data[] = { 0, 9, 8, 7, 6, 5, 4, 3, 2, 1 }; int length = sizeof(data) / sizeof(data[0]); bubbleSort(data, length); PrintArray(data,length); QuickSort(data, length, 0, length - 1); PrintArray(data, length); HeapSort(data, length); PrintArray(data, length); SelectSort(data, length); PrintArray(data, length); InsertSort(data, length); PrintArray(data, length); ShellSort(data, length); PrintArray(data, length); MergeSort(data, 0, length - 1); PrintArray(data,length); system("pause"); return 0; }