您现在的位置是:首页 >学无止境 >八大排序之交换排序与计数排序网站首页学无止境

八大排序之交换排序与计数排序

冷兮雪 2023-06-18 00:00:03
简介八大排序之交换排序与计数排序

 此篇更新完成后,八大排序已经全部写完,还请各位可以多多支持!🥰

八大排序之选择排序_冷兮雪的博客-CSDN博客

八大排序之插入排序和归并排序_冷兮雪的博客-CSDN博客

目录

交换排序的基本思想🍭

一、冒泡排序🍭

1、基本思想🍉

2、实现代码🍉

 3、代码优化🍉

4、优缺点🍉

5、算法分析🍉

6、 应用场景🍉

二、快速排序🍭

1、基本思想🍉

2、代码实现(递归与非递归)🍉

 3、代码优化🍉

4、优缺点🍉

5、算法分析🍉

 6、应用场景🍉

计数排序

1、基本思想🍉

2、代码实现🍉

 3、优缺点🍉

4、算法分析🍉

 5、应用场景


交换排序的基本思想🍭

交换排序是基于比较的排序算法,其主要思想是不断比较相邻两个元素的大小,将较小的元素不断交换到数组的前面,较大的元素不断交换到数组的后面,直到整个数组有序为止。

一、冒泡排序🍭

1、基本思想🍉

冒泡排序的基本思想是通过比较相邻的两个元素的大小,将较小的元素不断交换到数组的前面,较大的元素不断交换到数组的后面。具体地,排序过程如下:

  1. 比较相邻的两个元素,如果前一个元素比后一个元素大,则交换这两个元素的位置。
  2. 不断重复第一步,直到将最大的元素交换到数组的最后一个位置。
  3. 重复上述操作,每次将待排序的数组长度减一,直到整个数组有序为止。

2、实现代码🍉

    public static void bubbleSort(int[] arr) {
        int len = arr.length;
        for (int i = 0; i < len - 1; i++) {
            for (int j = 0; j < len - 1 - i; j++) {
                if (arr[j] > arr[j+1]) {
                    int temp = arr[j];
                    arr[j] = arr[j+1];
                    arr[j+1] = temp;
                }
            }
        }
    }

 3、代码优化🍉

 🧁冒泡排序的优化1:如果一次循环中没有发生交换,则说明数组已经有序,可以结束排序。

 优化前:

import java.util.Arrays;

public class Main {
    public static void bubbleSort(int[] arr) {
        int len = arr.length;
        for (int i = 0; i < len - 1; i++) {
            for (int j = 0; j < len - 1 - i; j++) {
                if (arr[j] > arr[j+1]) {
                    int temp = arr[j];
                    arr[j] = arr[j+1];
                    arr[j+1] = temp;
                }
                System.out.print("第 "+(i+1)+" 趟,第 "+(j+1)+" 次比较后的结果:");
                System.out.println(Arrays.toString(arr));
            }
        }
    }
    public static void main(String[] args) {
        int[] arr={2,9,7,15,49,10};
        System.out.println(Arrays.toString(arr));
        bubbleSort(arr);
    }
}

 

可以看到上方的代码打印,其实有不少循环过程未发生任何变化,且已排序完成,所以此时应该提前退出循环。

优化后:

public static void bubbleSort(int[] arr) {
    int n = arr.length;
    for (int i = 0; i < n - 1; i++) {
        boolean flag = false;
        for (int j = 0; j < n - 1 - i; j++) {
            if (arr[j] > arr[j + 1]) {
                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
                flag = true;
            }
        }
        if (!flag) {
            break;
        }
    }
}

 

 可以看到优化之后明显减少了排序的次数。

 🧁冒泡排序的优化2:记录每一次循环中最后一次交换的位置lastIndex,在下一次循环中,只需要比较到lastIndex的位置即可,因为lastIndex之后的元素已经有序。

public static void bubbleSort(int[] arr) {
    int n = arr.length;
    int lastIndex = 0;
    int k = n - 1;
    for (int i = 0; i < n - 1; i++) {
        boolean flag = false;
        for (int j = 0; j < k; j++) {
            if (arr[j] > arr[j + 1]) {
                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
                flag = true;
                lastIndex = j;
            }
        }
        if (!flag) {
            break;
        }
        k = lastIndex;
    }
}

4、优缺点🍉

冒泡排序的主要优点是代码简单易懂,实现方便,适用于小规模的数据排序。冒泡排序的主要缺点是时间复杂度较高,为 O(n²),不适用于大规模数据的排序。

5、算法分析🍉

1、时间复杂度

在最坏情况下,即待排序的序列是逆序的情况下,冒泡排序需要比较和交换的次数最多。在这种情况下,冒泡排序的时间复杂度为O(n²)。在最好情况下,即待排序的序列已经有序的情况下,冒泡排序只需要进行一次遍历,时间复杂度为O(n)

因此,冒泡排序的平均时间复杂度为O(n²)。虽然冒泡排序的时间复杂度较高,但对于小规模的数据排序,冒泡排序仍然是一种简单有效的排序算法。

2、空间复杂度

冒泡排序是一种原地排序算法,不需要额外的空间进行排序。因此,冒泡排序的空间复杂度为O(1)。

3、稳定性

冒泡排序是一种稳定的排序算法。由于冒泡排序只会交换相邻元素中大小关系不符合要求的元素,因此相同元素的相对位置不会发生变化,保证了冒泡排序的稳定性。

6、 应用场景🍉

  1. 教学和学习:冒泡排序是一种很好理解的排序算法,可以作为初学者学习排序算法的入门算法,帮助理解算法的基本思想。

  2. 小规模数组排序:对于小规模的待排序数组,冒泡排序的效率可能比较高,因为它的常数因子较小。

  3. 数据基本有序的排序:如果待排序数组中的元素已经基本有序,即每个元素与它前后的元素相差不大,那么冒泡排序的效率会比较高,因为它在对已排序的部分不会进行比较和交换。

总的来说,冒泡排序在实际应用中的使用场景较为有限,更多的是用于教学和算法实现方面。

二、快速排序🍭

快速排序是一种不稳定的排序算法,其基本原理是通过选取一个基准元素,将数组划分为两个子数组,分别对子数组进行排序,最终实现整个数组的有序排列。快速排序的时间复杂度为O(nlogn),是一种高效的排序算法。

1、基本思想🍉

快速排序的基本思想是:选择一个基准元素,将数组划分为两个子数组,比基准元素小的元素放在左边,比基准元素大的元素放在右边,然后分别对左右子数组进行排序,最终实现整个数组的有序排列。具体地,排序过程如下:

  1. 选择一个基准元素;
  2. 将数组划分为两个子数组,比基准元素小的元素放在左边,比基准元素大的元素放在右边;
  3. 分别对左右子数组进行排序,重复上述操作;
  4. 直到整个数组有序为止。

 

2、代码实现(递归与非递归)🍉

 🧁递归版  hoare版本(左右指针法):

public static void quickSort(int[] arr, int left, int right) {
    if (left >= right) return;

    int i = left, j = right;
    int pivot = arr[left]; // 选择数组的第一个元素作为基准

    while (i < j) {
        while (i < j && arr[j] >= pivot) j--; // 从右往左找到第一个小于pivot的数
        while (i < j && arr[i] <= pivot) i++; // 从左往右找到第一个大于pivot的数
        if (i < j) swap(arr, i, j); // 交换这两个数
    }

    swap(arr, left, i); // 把基准放到它正确的位置上,此时i=j

    quickSort(arr, left, i - 1); // 递归处理左半部分
    quickSort(arr, i + 1, right); // 递归处理右半部分
}

private static void swap(int[] arr, int i, int j) {
    int temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}

 网上一个经典的hoare版快排GIF(一趟快排)

 🧁 挖坑法

public static void quickSort(int[] arr, int left, int right) {
    if (left >= right) return;

    int i = left, j = right;
    int pivot = arr[left]; // 挖一个坑,选择数组的第一个元素作为基准

    while (i < j) {
        while (i < j && arr[j] >= pivot) j--; // 从右往左找到第一个小于pivot的数
        if (i < j) arr[i++] = arr[j]; // 把该数填到之前挖出来的坑中

        while (i < j && arr[i] <= pivot) i++; // 从左往右找到第一个大于pivot的数
        if (i < j) arr[j--] = arr[i]; // 把该数填到刚才挖出的坑中
    }

    arr[i] = pivot; // 将最初挖出来的坑填回去,此时i=j

    quickSort(arr, left, i - 1); // 递归处理左半部分
    quickSort(arr, i + 1, right); // 递归处理右半部分
}

【C语言】八大排序算法- 惊觉

🧁前后指针法:

第一种写法:

public static void quickSort(int[] arr, int start, int end) {
    if (start >= end) return;

    int pivot = arr[start]; // 选择数组的第一个元素作为基准

    int i = start, j = end;
    while (i < j) {
        while (i < j && arr[j] >= pivot) j--; // 从右往左找到第一个小于pivot的数
        while (i < j && arr[i] <= pivot) i++; // 从左往右找到第一个大于pivot的数
        if (i < j) swap(arr, i, j); // 交换这两个数
    }

    swap(arr, start, i); // 把基准放到它正确的位置上,此时i=j

    quickSort(arr, start, i - 1); // 排序左半部分
    quickSort(arr, i + 1, end); // 排序右半部分
}

private static void swap(int[] arr, int i, int j) {
    int temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}

第二种写法:

public static void quickSort(int[] arr, int start, int end) {
    if (start >= end) return;

    int pivot = arr[start]; // 选择数组的第一个元素作为基准

    int i = start + 1, j = start + 1; // i和j都从start+1开始
    while (j <= end) {
        if (arr[j] < pivot) {
            swap(arr, i, j);
            i++;
        }
        j++;
    }

    swap(arr, start, i - 1); // 把枢轴放到它正确的位置上

    quickSort(arr, start, i - 2); // 排序左半部分
    quickSort(arr, i, end); // 排序右半部分
}

private static void swap(int[] arr, int i, int j) {
    int temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}

第一种写法中,i和j都从start开始,用两个while循环找到需要交换的数,并且是在i和j相遇时才交换。

第二种写法中,i和j都从start+1开始,只有当arr[j]<pivot时才交换,交换后把i向前移动一位,最终i停留的位置就是基准的正确位置。 

八大排序算法(C语言实现)_2021dragon的博客-CSDN博客_排序算法c语言实现

🧁 非递归版:

public static void quickSort(int[] arr) {
    Stack<Integer> stack = new Stack<>();
    int left = 0, right = arr.length - 1;
    stack.push(left);
    stack.push(right);
    while (!stack.isEmpty()) {
        right = stack.pop();
        left = stack.pop();
        int pivot = partition(arr, left, right);
        // 将左子数组入栈
        if (left < pivot - 1) {
            stack.push(left);
            stack.push(pivot - 1);
        }
        // 将右子数组入栈
        if (right > pivot + 1) {
            stack.push(pivot + 1);
            stack.push(right);
        }
    }
}

public static int partition(int[] arr, int left, int right) {
    int pivot = arr[left];
    int i = left, j = right;
    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;
    return i;
}

使用一个Stack数据结构来模拟递归过程,实现非递归的快速排序。我们首先将数组的左边界和右边界入栈,然后从栈中取出左边界和右边界,进行划分数组的操作。划分完成后,将左子数组和右子数组的边界入栈,继续进行处理,直到栈为空。

非递归的快速排序算法的时间复杂度为O(nlogn),空间复杂度为O(logn),效率与递归版本的快速排序相当。

 3、代码优化🍉

  1. 优化1:如果待排序数组的长度小于某个常数,可以使用插入排序来替代快速排序。因为对于小规模的数据,插入排序的效率要高于快速排序。这个常数的取值可以根据实际情况进行调整。

  2. 优化2:随机选择基准点,避免数组已经有序或近似有序的情况下时间复杂度退化。在实际应用中,数组的分布情况是不可预知的,如果固定选择第一个或最后一个元素作为基准点,那么在一些特殊情况下,快速排序的效率会变得非常低。因此,我们可以随机选择一个元素作为基准点,避免这种情况的发生。

    public static void quickSort(int[] arr, int left, int right) {
        // 递归终止条件
        if (left >= right) return;
        // 优化1:如果待排序数组的长度小于某个常数,可以使用插入排序
        if (right - left + 1 <= 10) {
            insertionSort(arr, left, right);
            return;
        }
        int pivot = partition(arr, left, right);  // 划分数组
        quickSort(arr, left, pivot - 1);  // 递归处理左子数组
        quickSort(arr, pivot + 1, right);  // 递归处理右子数组
    }
    
    public static int partition(int[] arr, int left, int right) {
        // 优化2:随机选择基准点,避免数组已经有序或近似有序的情况下时间复杂度退化
        int pivot = arr[left + new Random().nextInt(right - left + 1)];
        int i = left, j = right;
        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;
        return i;
    }
    
    public static void insertionSort(int[] arr, int left, int right) {
        for (int i = left + 1; i <= right; i++) {
            int temp = arr[i];
            int j = i - 1;
            while (j >= left && arr[j] > temp) {
                arr[j + 1] = arr[j];
                j--;
            }
            arr[j + 1] = temp;
        }
    }

🧁 优化后的快速排序算法的时间复杂度为O(nlogn),空间复杂度为O(logn),效率比未优化的快速排序算法更高。

         3.优化三: 使用三数取中法来选择基准元素。然后使用两个指针 i 和 j 分别从左和右开始扫描数组,寻找需要交换的元素,最后将数组分成了两部分进行递归排序。

  public static void quicksort(int[] arr) {
            sort(arr, 0, arr.length-1);
        }

        private static void sort(int[] arr, int left, int right) {
            if (left >= right)
                return;

            // 选取枢轴元素
            int mid = left + (right - left) / 2;
            if (arr[right] < arr[left])
                swap(arr, left, right);
            if (arr[mid] < arr[left])
                swap(arr, mid, left);
            if (arr[right] < arr[mid])
                swap(arr, right, mid);

            int pivot = arr[mid];
            int i = left, j = right;
            while (true) {
                while (arr[i] < pivot)
                    i++;

                while (arr[j] > pivot)
                    j--;

                if (i >= j)
                    break;

                swap(arr, i, j);
                i++;
                j--;
            }

            sort(arr, left, i-1);
            sort(arr, i, right);
        }

        private static void swap(int[] arr, int i, int j) {
            int temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }

4、优缺点🍉

快速排序的主要优点是时间复杂度较低,为 O(nlogn),适用于大规模数据的排序。快速排序的主要缺点是不稳定,可能会改变相同元素的相对位置。

5、算法分析🍉

  1. 时间复杂度:快速排序的时间复杂度为O(nlogn),其中n为待排序数组的长度。最坏情况下,快速排序的时间复杂度为O(n^2),但这种情况出现的概率很小,可以通过一些优化措施来避免。

  2. 空间复杂度:快速排序的空间复杂度取决于递归栈的深度,在最坏情况下,递归栈的深度为O(n),因此快速排序的空间复杂度为O(n)。但是,在一些实现中,可以使用非递归的方式来实现快速排序,从而避免递归栈带来的空间开销。

  3. 稳定性:快速排序是一种不稳定的排序算法。因为在排序过程中,可能会交换相同元素的位置,从而导致相同元素的相对顺序被改变。例如,对于数组[3, 2, 2, 1],如果选择第一个元素3作为基准元素,那么经过第一次划分后,数组变成了[1, 2, 2, 3],其中两个2的相对顺序被改变了。

 6、应用场景🍉

  1. 大规模数据排序:快速排序的时间复杂度为 O(nlogn),在大规模数据排序时表现优秀。

  2. 数据重复性较少的排序:在排序的数据中,如果存在大量重复的元素,那么快速排序的效率会受到影响,因为这样会增加比较和交换的次数。

  3. 对数据随机性要求不高的排序:由于快速排序的分区过程是基于一个基准元素来完成的,因此如果待排序数据的分布比较随机,那么快速排序的效率会很高。

🧁总的来说,快速排序是一种高效的排序算法,在数据量较大、数据分布比较随机、重复性较少的场景中表现优秀,是一种很好的排序算法选择。

计数排序

1、基本思想🍉

计数排序又称为 鸽巢原理 ,是对哈希直接定址法的变形应用,是一种非基于比较的排序算法。 操作步骤:
  1. 统计相同元素出现次数
  2. 根据统计的结果将序列回收到原来的序列中

2、代码实现🍉

步骤:

  1. 找到数组中的最大值和最小值。
  2. 创建一个大小为(max-min+1)的桶,用于统计元素出现的次数。
  3. 遍历原数组,统计每个元素出现的次数,把它们放到对应的桶中。
  4. 对桶进行顺序求和,bucket[i]存放的就是原数组中小于等于i的元素个数。
  5. 从后往前遍历原数组,根据桶中统计的元素个数,将每个元素放到正确的位置上。
  6. 把排好序的元素复制回原数组。
 public static void countingSort(int[] arr) {
        if (arr == null || arr.length <= 1) return;

        // 找到数组中的最大值和最小值
        int max = arr[0], min = arr[0];
        for (int i = 1; i < arr.length; i++) {
            max = Math.max(max, arr[i]);
            min = Math.min(min, arr[i]);
        }

        int bucketSize = max - min + 1; // 桶的大小
        int[] bucket = new int[bucketSize]; // 创建桶

        // 统计每个元素出现的次数
        for (int i = 0; i < arr.length; i++) {
            bucket[arr[i] - min]++;
        }
        //System.out.println(Arrays.toString(bucket));//[1, 1, 0, 0, 1, 0, 1, 0, 2]

        // 对桶进行顺序求和,bucket[i]存放的就是原数组中小于等于i的元素个数
        for (int i = 1; i < bucketSize; i++) {
            bucket[i] += bucket[i - 1];
        }
        //System.out.println(Arrays.toString(bucket));//[1, 2, 2, 2, 3, 3, 4, 4, 6]

        int[] temp = new int[arr.length]; // 创建临时数组

        // 从后往前遍历原数组,根据桶中统计的元素个数,将每个元素放到正确的位置上
        for (int i = arr.length - 1; i >= 0; i--) {
            temp[--bucket[arr[i] - min]] = arr[i];
        }
        //System.out.println(Arrays.toString(temp));[1, 2, 5, 7, 9, 9]

        // 把排好序的元素复制回原数组
        for (int i = 0; i < arr.length; i++) {
            arr[i] = temp[i];
        }
    }

 3、优缺点🍉

计数排序的主要优点是时间复杂度第,稳定性好,适用于范围小的整数数据。计数排序的主要缺点是需要额外的存储空间(当数据范围大时,这一缺点将会无限放大),无法处理浮点型数据排序等其他类型的数据。

4、算法分析🍉

下面n是待排序数组的长度,k是桶的大小

1、时间复杂度:O(n+k)。

因为不需要比较操作,只需要遍历一次原数组,并对桶进行顺序求和和遍历,所以它的时间复杂度是O(n+k)。由于k通常比n要小,因此计数排序的时间复杂度可以看作是线性的。

2、空间复杂度:O(n+k)。

计数排序需要创建一个足够大的桶来存储每个元素出现的次数,因此空间复杂度与桶的大小有关。如果待排序数组中的最大值和最小值之间差距很大,那么桶的数量会增加,导致空间复杂度变高。另外,由于计数排序不需要比较操作,因此它不需要额外的存储空间来存储比较结果,所以只需要考虑桶的大小对空间复杂度的影响。

3、稳定性:计数排序是一种稳定的排序算法。

因为它在统计每个元素出现次数时,使用了桶来存储每个元素的出现次数。当有多个元素值相同时,它们会被放到同一个桶里,并按照原始输入的顺序存储在桶中。在遍历桶时,我们按照桶内元素统计的顺序,将每个元素放到正确的位置上,从而保证了排序的稳定性。

 5、应用场景

适用于范围小的整数数据。(原因优缺点处已写)

风语者!平时喜欢研究各种技术,目前在从事后端开发工作,热爱生活、热爱工作。