C++中实现10个整型的浮升序排列方法 |holyya.com

C++中实现10个整型的浮升序排列方法

2023-07-04 19:26:25 深夜i -- --

C++ 整型浮升序排列方法 10个

在C++编程中，排序算法是应用最频繁的算法之一。当涉及到大量数据的处理时，对数据进行排序可以使程序能够更加快速、准确地进行操作。而浮升序排列是最常用的排序模式之一，能够帮助我们快速对数据进行排序。本文将为大家讲解如何在C++中实现10个整型的浮升序排列方法。

1. 冒泡排序

冒泡排序是最简单的排序算法之一。它的基本思想是依次比较相邻的两个数，将较大的数交换到后面。可以使用循环语句实现该算法，如下所示：


void bubbleSort(int arr[], int n) {
  for(int i=0; i<n-1; i++) {
    for(int j=0; j<n-i-1; j++) {
      if(arr[j]>arr[j+1]) {
        int tmp = arr[j];
        arr[j] = arr[j+1];
        arr[j+1] = tmp;
      }
    }
  }
}

2. 插入排序

插入排序的基本思想是将待排序的元素插入到已排好序的数列中的正确位置。该算法的时间复杂度为O(n^2)，但它的常数项较小，因此在一定程度上具有优势。可以使用循环语句和条件语句实现该算法，如下所示：


void insertSort(int arr[], int n) {
  for(int i=1; i<n; i++) {
    int j = i;
    int tmp = arr[i];
    while(j>0 && tmp<arr[j-1]) {
      arr[j] = arr[j-1];
      j--;
    }
    arr[j] = tmp;
  }
}

3. 选择排序

选择排序的基本思想是选择最小的元素并将其交换到已排好序的数列的末尾。该算法的时间复杂度为O(n^2)，但由于它的交换次数较少，因此比冒泡排序要快。可以使用循环语句和条件语句实现该算法，如下所示：


void selectSort(int arr[], int n) {
  for(int i=0; i<n-1; i++) {
    int minIndex = i;
    for(int j=i+1; j<n; j++) {
      if(arr[j]<arr[minIndex]) {
        minIndex = j;
      }
    }
    if(minIndex != i) {
      int tmp = arr[i];
      arr[i] = arr[minIndex];
      arr[minIndex] = tmp;
    }
  }
}

4. 快速排序

快速排序是一种基于分治思想的排序算法。它的基本思想是选取一个枢轴元素，将待排序序列分为两部分，一部分元素的值都不大于枢轴，另一部分元素的值都不小于枢轴；然后递归地对两个子序列进行排序。该算法的时间复杂度为O(nlogn)，是目前应用最广泛的排序算法之一。可以使用递归函数实现该算法，如下所示：


void quickSort(int arr[], int left, int right) {
  if(left>=right) {
    return;
  }
  int pivot = partition(arr, left, right);
  quickSort(arr, left, pivot-1);
  quickSort(arr, pivot+1, right);
}
int partition(int arr[], int left, int right) {
  int pivot = arr[right];
  int i = left-1;
  for(int j=left; j<=right-1; j++) {
    if(arr[j]<pivot) {
      i++;
      int tmp = arr[i];
      arr[i] = arr[j];
      arr[j] = tmp;
    }
  }
  int tmp = arr[i+1];
  arr[i+1] = arr[right];
  arr[right] = tmp;
  return i+1;
}

5. 归并排序

归并排序也是一种基于分治思想的排序算法。它的基本思想是将待排序序列分为两部分，并对每个子序列递归地进行排序；然后将两个已排好序的子序列合并成一个有序序列。该算法的时间复杂度为O(nlogn)，但由于需要额外的空间存储序列，因此空间复杂度为O(n)。可以使用递归函数实现该算法，如下所示：


void mergeSort(int arr[], int left, int right) {
  if(left>=right) {
    return;
  }
  int mid = left+(right-left)/2;
  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* tmp = new int[right-left+1];
  int i = left, j = mid+1, k = 0;
  while(i<=mid && j<=right) {
    if(arr[i]<arr[j]) {
      tmp[k++] = arr[i++];
    } else {
      tmp[k++] = arr[j++];
    }
  }
  while(i<=mid) {
    tmp[k++] = arr[i++];
  }
  while(j<=right) {
    tmp[k++] = arr[j++];
  }
  for(int t=0; t<k; t++) {
    arr[left+t] = tmp[t];
  }
  delete[] tmp;
}

6. 希尔排序

希尔排序是一种改进的插入排序算法。它的基本思想是将待排序序列按照一定的步长进行分组，对于每组使用插入排序算法进行排序；随着步长的减小，每组包含的元素越来越少，当步长减小到1时，整个序列被分成一组，此时使用插入排序算法对其进行排序。该算法的时间复杂度为O(nlogn)到O(n^2)，具体取决于步长的选取。可以使用循环语句和条件语句实现该算法，如下所示：


void shellSort(int arr[], int n) {
  int gap = n/2;
  while(gap>=1) {
    for(int i=gap; i<n; i++) {
      int j = i;
      int tmp = arr[i];
      while(j>=gap && tmp<arr[j-gap]) {
        arr[j] = arr[j-gap];
        j -= gap;
      }
      arr[j] = tmp;
    }
    gap /= 2;
  }
}

7. 堆排序

堆排序是一种基于完全二叉树的排序算法。它的基本思想是将待排序序列建立成一个堆，并使用堆的性质进行排序；具体来说，每次从堆中删除堆顶元素（最大元素）并放到序列的末尾，然后对堆进行调整。该算法的时间复杂度为O(nlogn)，但由于需要额外的空间存储堆，因此空间复杂度为O(n)。可以使用循环语句和条件语句实现该算法，如下所示：


void heapSort(int arr[], int n) {
  for(int i=n/2-1; i>=0; i--) {
    adjustHeap(arr, i, n);
  }
  for(int i=n-1; i>=1; i--) {
    int tmp = arr[0];
    arr[0] = arr[i];
    arr[i] = tmp;
    adjustHeap(arr, 0, i);
  }
}
void adjustHeap(int arr[], int i, int n) {
  int tmp = arr[i];
  for(int j=2*i+1; j<n; j=2*j+1) {
    if(j+1<n && arr[j]<arr[j+1]) {
      j++;
    }
    if(tmp>=arr[j]) {
      break;
    }
    arr[i] = arr[j];
    i = j;
  }
  arr[i] = tmp;
}

8. 计数排序

计数排序是一种非比较排序算法。它的基本思想是将待排序序列中元素出现的次数计数，然后依次输出。具体来说，我们可以先找出待排序序列中的最大值max，然后申请一个长度为max+1的桶，用于存放待排序元素的出现次数；然后遍历原始序列，将每个数作为桶的下标，将桶中对应位置的数加1；最后遍历桶，按照桶的下标依次输出数值。该算法的时间复杂度为O(n+k)，其中k为桶的大小。可以使用循环语句和条件语句实现该算法，如下所示：


void countSort(int arr[], int n) {
  int max = arr[0];
  for(int i=1; i<n; i++) {
    if(arr[i]>max) {
      max = arr[i];
    }
  }
  int* tmp = new int[max+1];
  for(int i=0; i<=max; i++) {
    tmp[i] = 0;
  }
  for(int i=0; i<n; i++) {
    tmp[arr[i]]++;
  }
  int j = 0;
  for(int i=0; i<=max; i++) {
    while(tmp[i]--) {
      arr[j++] = i;
    }
  }
  delete[] tmp;
}

9. 桶排序

桶排序也是一种非比较排序算法。它的基本思想是将待排序序列划分为若干个桶，然后对每个桶单独进行排序；排完序后，依次输出每个桶的元素，得到最终有序序列。该算法的时间复杂度为O(n)，但它需要额外的空间存储桶，因此空间复杂度为O(n)。可以使用循环语句和条件语句实现该算法，如下所示：


void bucketSort(int arr[], int n, int bucketSize) {
  int min = arr[0], max = arr[0];
  for(int i=1; i<n; i++) {
    if(arr[i]<min) {
      min = arr[i];
    } else if(arr[i]>max) {
      max = arr[i];
    }
  }
  int bucketCount = (max-min)/bucketSize+1;
  vector<vector<int>> buckets(bucketCount);
  for(int i=0; i<n; i++) {
    int idx = (arr[i]-min)/bucketSize;
    buckets[idx].push_back(arr[i]);
  }
  int k = 0;
  for(int i=0; i<bucketCount; i++) {
    sort(buckets[i].begin(), buckets[i].end());
    for(int j=0; j<buckets[i].size(); j++) {
      arr[k++] = buckets[i][j];
    }
  }
}

10. 基数排序

基数排序是一种非比较排序算法，它的基本思想是将待排序序列依次按照个位、十位、百位等进行排序。具体来说，我们可以先找出待排序序列中最大数的位数maxDigit，然后从个位开始依次取出数位，使用计数排序对每个数位进行排序；每次排序后，将排序结果写回原始序列，直到所有数位均被排序。该算法的时间复杂度为O(d*(n+k))，其中d为最大位数，k为基数大小。可以使用循环语句、条件语句和递归函数实现该算法，如下所示：


void radixSort(int arr[], int n) {
  int max = arr[0];
  for(int i=1; i<n; i++) {
    if(arr[i]>max) {
      max = arr[i];
    }
  }
  int maxDigit = 0;
  while(max>0) {
    maxDigit++;
    max /= 10;
  }
  int* tmp = new int[n];
  int* count = new int[10];
  int radix = 1;
  for(int i=1; i<=maxDigit; i++) {
    for(int j=0; j<10; j++) {
      count[j] = 0;
    }
    for(int j=0; j<n; j++) {
      int k = (arr[j]/radix)%10;
      count[k]++;
    }
    for(int j=1; j<10; j++) {
      count[j] += count[j-1];
    }
    for(int j=n-1; j>=0; j--) {
      int k = (arr[j]/radix)%10;
      tmp[count[k]-1] = arr[j];
      count[k]--;
    }
    for(int j=0; j<n; j++) {
      arr[j] = tmp[j];
    }
    radix *= 10;
  }
  delete[] tmp;
  delete[] count;
}

综上所述，C++中实现10个整型的浮升序排列方法，包括冒泡排序、插入排序、选择排序、快速排序、归并排序、希尔排序、堆排序、计数排序、桶排序和基数排序。每种算法都有不同的优点和适用场景，需要根据实际情况进行选择。在编写排序算法时，需要注意算法复杂度、空间复杂度、稳定性等因素。掌握这些排序方法，将有助于提高程序运行效率，优化算法操作。

上一篇: idea打包java可执行jar包

下一篇: Vue和Node.js联合开发的网站项目

评论区

()

相似文章