21xrx.com
2024-09-20 00:43:42 Friday
登录
文章检索 我的文章 写文章
C++ 数组排序代码
2023-07-01 20:56:58 深夜i     --     --
C++ 数组 排序 代码

C++数组排序代码

在C++编程中，数组排序是一项基本任务，因为经常需要对一个数组中的元素按照一定规则进行排序。下面是一段常用的C++数组排序代码，可以实现快速排序、归并排序和插入排序。

#include

using namespace std;

//快速排序

void quickSort(int arr[], int left, int right) {

  int i = left, j = right;

  int tmp;

  int pivot = arr[(left + right) / 2];

  /* partition */

  while (i <= j) {

    while (arr[i] < pivot)

      i++;

    while (arr[j] > pivot)

      j--;

    if (i <= j) {  // 交换左右两边的元素

      tmp = arr[i];

      arr[i] = arr[j];

      arr[j] = tmp;

      i++;

      j--;

    }

  };

  /* recursion */

  if (left < j)

    quickSort(arr, left, j);

  if (i < right)

    quickSort(arr, i, right);

}

//归并排序

void merge(int arr[], int left, int middle, int right) {

  int i, j, k;

  int n1 = middle - left + 1;

  int n2 = right - middle;

  /* create temp arrays */

  int L[n1], R[n2];

  /* Copy data to temp arrays L[] and R[] */

  for (i = 0; i < n1; i++)

    L[i] = arr[left + i];

  for (j = 0; j < n2; j++)

    R[j] = arr[middle + 1+ j];

  /* Merge the temp arrays back into arr[l..r]*/

  i = 0; // Initial index of first subarray

  j = 0; // Initial index of second subarray

  k = left; // Initial index of merged subarray

  while (i < n1 && j < n2) {

    if (L[i] <= R[j]) {

      arr[k] = L[i];

      i++;

    }

    else {

      arr[k] = R[j];

      j++;

    }

    k++;

  }

  /* Copy the remaining elements of L[], if there are any */

  while (i < n1) {

    arr[k] = L[i];

    i++;

    k++;

  }

  /* Copy the remaining elements of R[], if there are any */

  while (j < n2) {

    arr[k] = R[j];

    j++;

    k++;

  }

}

void mergeSort(int arr[], int left, int right) {

  if (left < right) {

    int middle = left + (right - left) / 2;

    // Sort first and second halves

    mergeSort(arr, left, middle);

    mergeSort(arr, middle + 1, right);

    merge(arr, left, middle, right);

  }

}

//插入排序

void insertionSort(int arr[], int n) {

  int i, key, j;

  for (i = 1; i < n; i++) {

    key = arr[i];

    j = i - 1;

    /* Move elements of arr[0..i-1], that are greater than key, to one position ahead

      of their current position */

    while (j >= 0 && arr[j] > key) {

      arr[j + 1] = arr[j];

      j--;

    }

    arr[j + 1] = key;

  }

}

int main() {

  int arr[] = 23;

  int n = sizeof(arr)/sizeof(arr[0]);

  //quickSort(arr, 0, n-1);

  //mergeSort(arr, 0, n-1);

  //insertionSort(arr, n);

  cout << "Sorted array: \n";

  for (int i=0; i < n; i++)

    cout << arr[i] << " ";

  cout << endl;

  return 0;

}

可以看到，这段代码中，定义了三种不同的排序算法：快速排序、归并排序和插入排序。在主函数中，我们可以选择其中一种来对数组进行排序。

快速排序是一种高效的排序算法，其时间复杂度为O(nlogn)，但在最坏情况下（如数组已经有序），时间复杂度可能会变为O(n^2)。归并排序则是一种比较稳定的排序算法，其时间复杂度为O(nlogn)，但需要较多的空间来存储临时数组。插入排序则是一种简单粗暴的排序算法，其时间复杂度为O(n^2)，但适用于小规模数据排序。

在输入了待排序的数组后，只需要调用对应的排序函数即可得到排好序的数组，非常方便。

  
  

评论区

{{item['qq_nickname']}}
()
回复
回复