21xrx.com
2024-11-22 03:15:26 Friday
登录
文章检索 我的文章 写文章
C++类实现多种排序方式
2023-06-27 06:57:45 深夜i     --     --
C++ class sort multiple algorithms implementation

C++是一种非常流行的编程语言,可以用于实现各种算法和数据结构。其中,排序算法是非常重要且常用的一种算法。C++中可以使用类实现多种排序方式,这种实现方式具有以下优点:

1. 可扩展性:通过类的继承和多态性,可以方便地实现新的排序算法。

2. 健壮性:使用类可以将一些状态信息封装在对象中,从而保证排序算法的正确性。

3. 可重用性:由于排序算法经常被使用,使用类可以更方便地进行复用,从而减少代码量和开发时间。

下面是使用类实现三种常见的排序算法的示例代码:

1. 冒泡排序

class BubbleSort

{

public:

  static void sort(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]) {

          std::swap(arr[j], arr[j + 1]);

        }

      }

    }

  }

};

2. 快速排序

class QuickSort

{

public:

  static void sort(int arr[], int left, int right) {

    if (left >= right) return;

    int i = left, j = right, pivot = arr[left];

    while (i < j) {

      while (i < j && arr[j] >= pivot) --j;

      if (i < j) arr[i++] = arr[j];

      while (i < j && arr[i] <= pivot) ++i;

      if (i < j) arr[j--] = arr[i];

    }

    arr[i] = pivot;

    sort(arr, left, i - 1);

    sort(arr, i + 1, right);

  }

};

3. 插入排序

class InsertionSort

{

public:

  static void sort(int arr[], int n) {

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

      int key = arr[i];

      int j = i - 1;

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

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

        j--;

      }

      arr[j + 1] = key;

    }

  }

};

以上三种排序算法都是比较常见和基础的排序算法,使用类进行封装,可以提高程序代码的可读性和可维护性。如果我们想要使用其他排序算法,只需要实现一个新的类并继承自排序类即可。例如,如果我们想使用归并排序,则可以定义一个类如下:

class MergeSort : public Sort

{

public:

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

    if (left >= right) return;

    int mid = (left + right) / 2;

    sort(arr, left, mid);

    sort(arr, mid + 1, right);

    merge(arr, left, mid, right);

  }

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

    int temp[right - left + 1];

    int i = left, j = mid + 1, k = 0;

    while (i <= mid && j <= right) {

      if (arr[i] < arr[j]) temp[k++] = arr[i++];

      else temp[k++] = arr[j++];

    }

    while (i <= mid) temp[k++] = arr[i++];

    while (j <= right) temp[k++] = arr[j++];

    for (i = 0; i < k; i++) {

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

    }

  }

};

以上示例说明了使用排序类的优点,也展示了如何实现排序类。使用类进行封装,可以使代码更加清晰、可读性更高,提高了程序的可维护性。

  
  

评论区

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