算法-排序与双指针

左手的ㄟ右手 2024-03-16 17:09 20阅读 0赞

## **n平方复杂度的排序有哪些？**  ##

n平方复杂度的排序算法包括：

1.  冒泡排序（Bubble Sort）：比较相邻的元素，如果前一个比后一个大，就交换它们的位置，重复进行直到排序完成。
2.  选择排序（Selection Sort）：每次从未排序的元素中选择最小的元素，放到已排序的末尾，重复进行直到排序完成。
3.  插入排序（Insertion Sort）：将未排序的元素插入到已排序的合适位置，重复进行直到排序完成。
4.  希尔排序（Shell Sort）：将待排序的元素按照一定的间隔分组，对每组进行插入排序，逐渐缩小间隔，直到间隔为1，最后进行一次插入排序。
5.  快速排序（Quick Sort）：选择一个基准元素，将小于基准元素的放在左边，大于基准元素的放在右边，对左右两个子序列递归进行快速排序。

这些排序算法的时间复杂度都是O(n^2)，其中冒泡排序、选择排序和插入排序是比较简单的排序算法，但效率较低，适用于小规模数据的排序；希尔排序是插入排序的改进版，效率比前三种算法要高一些；快速排序是一种高效的排序算法，虽然最坏情况下时间复杂度也是O(n^2)，但平均情况下时间复杂度为O(nlogn)，是常用的排序算法之一。

## **如何实现冒泡排序，如何进行优化？**  ##

冒泡排序是一种简单的排序算法，其基本思想是通过相邻元素之间的比较和交换来将较大的元素逐步“冒泡”到数组的末尾，从而实现排序。具体实现过程如下：

1.  从数组的第一个元素开始，依次比较相邻的两个元素，如果前一个元素比后一个元素大，则交换它们的位置。
2.  继续比较下一对相邻元素，重复上述操作，直到将最大的元素“冒泡”到数组的末尾。
3.  重复执行上述操作，直到整个数组排序完成。

以下是一个简单的JavaScript实现冒泡排序的示例代码：

在这个实现中，bubbleSort函数接受一个数组arr作为参数，并返回一个排序后的数组。这个函数使用两层循环来实现冒泡排序，外层循环控制排序的轮数，内层循环控制每一轮比较的次数。如果相邻的两个元素顺序不对，则交换它们的位置。

冒泡排序的时间复杂度为O(n^2)，在处理大规模数据时效率较低。为了提高冒泡排序的效率，可以进行以下优化：

1.  设置标志位：如果在一轮排序中没有发生任何交换，说明数组已经有序，可以直接退出循环。
2.  设置边界：每一轮排序后，最后一个元素已经是有序的，可以将下一轮排序的边界设置为上一轮排序的最后一个元素。
3.  鸡尾酒排序：在冒泡排序的基础上，每一轮排序既从左往右进行比较和交换，又从右往左进行比较和交换，可以更快地将较小的元素“冒泡”到数组的前面。

这些优化可以提高冒泡排序的效率，但时间复杂度仍然是O(n^2)。因此，在处理大规模数据时，应该选择更高效的排序算法。

## **如何实现选择排序和插入排序？**  ##

选择排序

选择排序的基本思想是每次从未排序的元素中选择最小的元素，将其放到已排序的元素末尾。具体实现过程如下：

*  从数组的第一个元素开始，依次遍历数组中的每个元素，将当前元素设为最小值。
 *  继续遍历数组，如果找到比当前元素更小的元素，则将其设为最小值。
 *  遍历完成后，将最小值与数组的第一个元素交换位置，将其放到已排序的元素末尾。
 *  重复执行上述操作，直到整个数组排序完成。

以下是一个简单的JavaScript实现选择排序的示例代码：

在这个实现中，selectionSort函数接受一个数组arr作为参数，并返回一个排序后的数组。这个函数使用两层循环来实现选择排序，外层循环控制排序的轮数，内层循环控制每一轮比较的次数。在每一轮比较中，找到未排序元素中的最小值，并将其放到已排序元素的末尾。

选择排序的时间复杂度为O(n^2)，与冒泡排序相同。但是，选择排序的交换次数比冒泡排序少，因此在某些情况下，选择排序的效率可能会更高。

插入排序

插入排序的基本思想是将未排序的元素插入到已排序的元素中，使得已排序的元素仍然有序。具体实现过程如下：

*  从数组的第二个元素开始，依次遍历数组中的每个元素，将当前元素插入到已排序的元素中。
 *  在已排序的元素中，从后往前遍历，找到当前元素应该插入的位置。
 *  将当前元素插入到已排序的元素中，使得已排序的元素仍然有序。
 *  重复执行上述操作，直到整个数组排序完成。

以下是一个简单的JavaScript实现插入排序的示例代码：

在这个实现中，insertionSort函数接受一个数组arr作为参数，并返回一个排序后的数组。这个函数使用两层循环来实现插入排序，外层循环控制排序的轮数，内层循环控制每一轮比较的次数。在每一轮比较中，找到当前元素应该插入的位置，并将其插入到已排序的元素中。

插入排序的时间复杂度为O(n^2)，与冒泡排序和选择排序相同。但是，插入排序的交换次数比冒泡排序和选择排序少，因此在某些情况下，插入排序的效率可能会更高。

## **n\*logn复杂读的排序有哪些？**  ##

n\*logn复杂度的排序算法有以下几种：

1.  快速排序

快速排序是一种基于分治思想的排序算法，其基本思想是选择一个基准元素，将数组分成两个子数组，其中一个子数组中的所有元素都小于基准元素，另一个子数组中的所有元素都大于基准元素。然后递归地对子数组进行排序，最终将整个数组排序完成。快速排序的时间复杂度为O(n\*logn)，但是在最坏情况下，时间复杂度可能会退化为O(n^2)。

2. 归并排序

归并排序是一种基于分治思想的排序算法，其基本思想是将数组分成两个子数组，递归地对子数组进行排序，然后将两个有序的子数组合并成一个有序的数组。归并排序的时间复杂度为O(n\*logn)，但是需要额外的空间来存储临时数组。

3. 堆排序

堆排序是一种基于堆的数据结构的排序算法，其基本思想是将数组构建成一个堆，然后依次将堆顶元素取出并放到已排序的元素中。堆排序的时间复杂度为O(n\*logn)，但是需要额外的空间来存储堆。

4.希尔排序

希尔排序是一种基于插入排序的排序算法，其基本思想是将数组分成若干个子数组，对每个子数组进行插入排序，然后逐步缩小子数组的范围，最终将整个数组排序完成。希尔排序的时间复杂度为O(n\*logn)，但是其时间复杂度的分析比较困难。

以上是常见的n\*logn复杂度的排序算法，它们都具有较高的效率和稳定性，可以应用于各种排序场景。

## **如何实现快速排序和归并排序？**  ##

快速排序的实现：

1.  选择一个基准元素，通常选择第一个或最后一个元素。
2.  将数组分成两个子数组，其中一个子数组中的所有元素都小于基准元素，另一个子数组中的所有元素都大于基准元素。
3.  递归地对子数组进行排序，最终将整个数组排序完成。

代码实现：

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);
    }

归并排序的实现：

1.  将数组分成两个子数组。
2.  递归地对子数组进行排序。
3.  将两个有序的子数组合并成一个有序的数组。

代码实现：

void merge(int arr[], int left, int mid, int right) {
        int i, j, k;
        int n1 = mid - left + 1;
        int n2 = right - mid;
    
        /* 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[mid + 1 + j];
    
        /* merge the temp arrays back into arr[left..right]*/
        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 mid = left + (right - left) / 2;
    
            /* sort first and second halves */
            mergeSort(arr, left, mid);
            mergeSort(arr, mid + 1, right);
    
            /* merge the sorted halves */
            merge(arr, left, mid, right);
        }
    }

## **复杂度为n的排序算法有哪些？具体的思路是什么样的？** ##

复杂度为n的排序算法有计数排序、桶排序和基数排序。计数排序的思路是统计每个元素出现的次数，然后根据元素出现的次数将元素放入相应的位置。具体实现时，需要先确定待排序数组中最大元素的值max，然后创建一个长度为max+1的计数数组count，遍历待排序数组，统计每个元素出现的次数，最后根据计数数组将元素放入相应的位置。

桶排序的思路是将待排序数组分成若干个桶，每个桶内部使用其他排序算法进行排序，最后将所有桶中的元素按照顺序依次放入待排序数组中。具体实现时，需要先确定桶的数量和每个桶的范围，然后遍历待排序数组，将每个元素放入相应的桶中，最后对每个桶内部使用其他排序算法进行排序，最后将所有桶中的元素按照顺序依次放入待排序数组中。

基数排序的思路是将待排序数组按照位数从低到高依次进行排序，具体实现时，需要先确定待排序数组中最大元素的位数maxDigit，然后从个位开始，对每一位进行排序，最后得到有序数组。具体实现时，可以使用桶排序对每一位进行排序，也可以使用计数排序对每一位进行排序。

## **快速排序和归并排序的区别是什么？**  ##

快速排序和归并排序都是常用的排序算法，它们的区别主要在于排序的方式和实现方法。快速排序的思路是选取一个基准元素，将待排序数组分成两部分，一部分小于基准元素，一部分大于基准元素，然后对这两部分分别进行递归排序，最后将排序好的两部分合并起来。具体实现时，可以选取第一个元素或者随机选取一个元素作为基准元素，然后使用双指针法将数组分成两部分，再递归排序这两部分。

归并排序的思路是将待排序数组分成若干个子数组，对每个子数组进行排序，然后将排好序的子数组合并起来，最终得到有序数组。具体实现时，可以使用递归将数组分成两部分，对每个子数组进行排序，然后使用归并操作将排好序的子数组合并起来。

快速排序的时间复杂度为O(nlogn)，空间复杂度为O(logn)，归并排序的时间复杂度也为O(nlogn)，但空间复杂度为O(n)。因此，在空间有限的情况下，快速排序更适合使用；而在空间充足的情况下，归并排序更适合使用。

## **返回arr的最长无重复元素子数组的长度**  ##

可以使用滑动窗口的思想来解决这个问题。定义一个左指针left和一个右指针right，表示当前子数组的左右边界。遍历数组，每次将右指针向右移动一位，如果当前元素不在子数组中，则将右指针继续向右移动；如果当前元素在子数组中，则将左指针向右移动，直到子数组中不包含当前元素为止。每次移动右指针时，都记录当前子数组的长度，并更新最长无重复元素子数组的长度。最终返回最长无重复元素子数组的长度即可。

具体实现时，可以使用一个哈希表来记录每个元素最后一次出现的位置，如果当前元素在哈希表中已经存在，则更新左指针的位置为当前元素最后一次出现的位置加一。每次移动右指针时，都更新当前元素的最后一次出现位置。时间复杂度为O(n)，空间复杂度为O(n)。以下是代码实现：

## **无重复最长子串**  ##

可以使用滑动窗口的思想来解决这个问题。定义一个左指针left和一个右指针right，表示当前子串的左右边界。遍历字符串，每次将右指针向右移动一位，如果当前字符不在子串中，则将右指针继续向右移动；如果当前字符在子串中，则将左指针向右移动，直到子串中不包含当前字符为止。每次移动右指针时，都记录当前子串的长度，并更新最长无重复字符子串的长度。最终返回最长无重复字符子串即可。

具体实现时，可以使用一个哈希表来记录每个字符最后一次出现的位置，如果当前字符在哈希表中已经存在，则更新左指针的位置为当前字符最后一次出现的位置加一。每次移动右指针时，都更新当前字符的最后一次出现位置。时间复杂度为O(n)，空间复杂度为O(n)。以下是代码实现：

## **最长上升子序列**  ##

最长上升子序列问题是指在一个给定的序列中，找到一个最长的子序列，使得这个子序列中的元素是递增的。可以使用动态规划来解决这个问题。

定义一个数组dp，其中dp\[i\]表示以第i个元素为结尾的最长上升子序列的长度。初始时，dp数组中的每个元素都为1，因为每个元素本身都可以作为一个长度为1的上升子序列。

然后遍历整个序列，对于每个元素i，从0到i-1遍历之前的元素j，如果当前元素i大于元素j，说明可以将元素i加入到以元素j为结尾的最长上升子序列中，此时更新dp\[i\]的值为dp\[j\]+1。最终dp数组中的最大值即为最长上升子序列的长度。

时间复杂度为O(n^2)，空间复杂度为O(n)。以下是代码实现：

## **盛水最多的容器** ##

盛水最多的容器问题是指在一个给定的数组中，找到两个数，使得它们组成的容器可以盛最多的水。可以使用双指针来解决这个问题。

定义两个指针left和right，分别指向数组的左右两端。计算当前容器的容量，即min(height\[left\], height\[right\]) \* (right - left)，并更新最大容量maxArea的值。然后移动指针，如果height\[left\] < height\[right\]，则left++，否则right--。重复上述步骤直到left >= right。

时间复杂度为O(n)，空间复杂度为O(1)。以下是代码实现：