如何用C++实现十大排序算法

如何用C++实现十大排序算法

这篇文章主要讲解了“如何用C++实现十大排序算法”，文中的讲解内容简单清晰，易于学习与理解，下面请大家跟着小编的思路慢慢深入，一起来研究和学习“如何用C++实现十大排序算法”吧！

冒泡排序

// 冒泡排序  // 从小到大  // 时间复杂度 平均 n^2 最好 n 最坏n^2  // 空间复杂度 1  // 内排序，稳定排序  void bubbleSort(int arr[] , int length) {      for (int i = 0; i < length - 1; ++i) {          for (int j = i; j < length; ++j) {              if (arr[i] > arr[j]){                  swap(arr[i],arr[j]);              }          }      }  }

选择排序

//选择排序  // 时间复杂度 平均 n^2 最好 n^2 最坏n^2  // 空间复杂度 1  // 内排序 不稳定  void selectSort(int arr[], int length) {      for (int i = 0; i < length; ++i) {          int minIndex = i;          for (int j = i; j < length; ++j) {              if (arr[minIndex] > arr[j]) {                  minIndex = j;              }          }          swap(arr[i], arr[minIndex]);      }  }

插入排序

// 插入排序  // 时间复杂度 平均 n^2 最好 n 最坏n^2  // 空间复杂度 1  // 内排序，稳定排序  void insertSort(int arr[], int length) {      for (int i = 1; i < length; ++i) {          int preIndex = i - 1;          int current = arr[i];          while (preIndex >= 0 && current <= arr[preIndex]) {              arr[preIndex + 1] = arr[preIndex];              preIndex--;          }          arr[preIndex + 1] = current;        }  }

希尔排序

// 希尔排序  // 时间复杂度 平均 n^1.3 最好 n 最坏n^2  // 空间复杂度 1  // 内排序，不稳定排序  void shellSort(int arr[], int length) {      for (int step = length / 2; step >= 1; step /= 2) {          for (int i = step; i < length; ++i) {              int preIndex = i - step;              int current = arr[i];              while (preIndex >= 0 && current <= arr[preIndex]) {                  arr[preIndex + step] = arr[preIndex];                  preIndex -= step;              }              arr[preIndex + step] = current;          }      }  }

归并排序

// 归并排序  // 时间复杂度 平均 nlogn 最好 nlogn 最坏 nlogn  // 空间复杂度 n  // 稳定 外排序  void mergeSort(int arr[], int left, int right) {      if (left >= right) {          return;      }      int mid = (left + right) >> 1;      mergeSort(arr, left, mid);      mergeSort(arr, mid + 1, right);      merge(arr, left, mid, right);    }    void merge(int *arr, int left, int mid, int right) {      int res[right - left + 1];      int left_index = left;      int right_index = mid + 1;      int index = 0;      while (left_index <= mid && right_index <= right) {          if (arr[left_index] < arr[right_index]) {              res[index] = arr[left_index];              index++;              left_index++;          } else {              res[index] = arr[right_index];              index++;              right_index++;          }      }      while (left_index <= mid) {          res[index] = arr[left_index];          index++;          left_index++;      }      while (right_index <= right) {          res[index] = arr[right_index];          index++;          right_index++;      }      for (int i = 0; i < right - left + 1; ++i) {          arr[left + i] = res[i];      }  }

快速排序

// 快速排序  // 时间复杂度 平均nlogn 最好nlogn 最坏 n^2  // 空间复杂度 logn  // 内排序 不稳定  void quickSort(int arr[], int left, int right) {      if (left >= right) {          return;      }      int p = arr[left];      int low = left, high = right;      while (low < high) {          while (low < high && arr[high] >= p) high--;          arr[low] = arr[high];          while (low < high && arr[low] <= p) low++;          arr[high] = arr[low];      }      arr[low] = p;      quickSort(arr, left, low - 1);      quickSort(arr, low + 1, right);  }

堆排序

// 堆排序  // 时间复杂度 平均nlogn 最好nlogn 最坏 nlogn  // 空间复杂度 1  // 内排序 不稳定  void heapify(int arr[], int i, int length) {      int left = 2 * i + 1;      int right = 2 * i + 2;      int max_index = i;      if (left < length && arr[max_index] < arr[left]) {          max_index = left;      }      if (right < length && arr[max_index] < arr[right]) {          max_index = right;      }      if (max_index != i) {          swap(arr[i], arr[max_index]);          heapify(arr, max_index, length);      }    }    void heap_sort(int arr[], int length) {      for (int i = length / 2 - 1; i >= 0; --i) {          heapify(arr, i, length);      }// 构建小顶堆      for (int i = length - 1; i > 0; --i) {          swap(arr[0], arr[i]);          heapify(arr, 0, i);      }    }

感谢各位的阅读，以上就是“如何用C++实现十大排序算法”的内容了，经过本文的学习后，相信大家对如何用C++实现十大排序算法这一问题有了更深刻的体会，具体使用情况还需要大家实践验证。这里是高防服务器网，小编将为大家推送更多相关知识点的文章，欢迎关注！

[微信提示：高防服务器能助您降低 IT 成本，提升运维效率，使您更专注于核心业务创新。

[图文来源于网络，不代表本站立场，如有侵权，请联系高防服务器网删除]
[