Temu bual Meituan: Sila tulis jadual cepat dengan tangan, saya terkejut!

Hari ini, penemu duga meminta saya menulis ringkasan di tempat kejadian adalah seperti berikut:

Pewawancara: Mari kita teruskan bercakap tentang struktur data dan algoritma. (Sambil bercakap, dia membelek resume saya dan menghulurkan pen, bermakna dia meminta saya menulis di belakang resume saya)

Rookie me: Apa maksud awak? Tulis di sini? (Sambil menunjuk resume)

Penemuduga: Yeah

Rookie me: No

Interviewer: Okay, itu sahaja untuk temuduga hari ini

Rookie me: (Saya sangat marah, saya nak letak pada pengurusan buruh saya. resume Penulisan kod? ) Shadiao

Penemuduga: (Memandang ke belakang, keliru)

Fikirkan, saya masih terlalu muda, tidak akan jadi seperti ini sekarang. Tulis sahaja, ia hanya sekeping kertas.

Sebenarnya, walaupun beratur cepat adalah mudah, saya rasa ramai orang tidak boleh menulisnya dengan tangan Adakah ramai orang yang boleh menulisnya dengan tangan di tempat dalam beberapa cara. .

Sekarang, mari analisa dan analisa ---- susun pantas.

Dari Ensiklopedia:

Isih cepat telah dicadangkan oleh C. A. R. Hoare pada tahun 1962. Idea asasnya adalah untuk membahagikan data untuk diisih kepada dua bahagian bebas melalui satu pengisihan Semua data dalam satu bahagian adalah lebih kecil daripada semua data di bahagian lain, dan kemudian menggunakan kaedah ini untuk memisahkan dua bahagian data dengan cepat. . Isih, keseluruhan proses pengisihan boleh dilakukan [secara rekursif], supaya keseluruhan data menjadi urutan tersusun.

Agak sukar untuk memahami konsep ini.

Ia boleh difahami seperti ini:

Isih cepat ialah versi jenis gelembung yang dipertingkatkan Keseluruhan prosesnya adalah untuk mengalih keluar dan menampal sesuatu, mengoyakkannya dan menampalnya, mengoyakkannya dan menampalnya, sehingga. semua elemen mencapai keadaan tertib.

Idea teras:

Mula-mula ambil nombor daripada jujukan sebagai nombor asas, dan kemudian lakukan pembahagian saiz

Dalam proses pembahagian, semua nombor yang lebih besar daripada nombor ini diletakkan di sebelah kanannya, dan nombor yang lebih kecil daripada; atau sama dengannya adalah Letakkan semuanya ke kiri;

Ulang langkah kedua untuk selang kiri dan kanan sehingga hanya terdapat satu nombor dalam setiap selang, dan pengisihan selesai.

Kes pelaksanaan

Mari kita bongkar langkah demi langkah melalui gambar dan teks.

Ambil [4,1,6,2,9,3]susunan ini sebagai contoh.

Hantaran pertama:

• Pecah pertama [4,1,6,2,9,3] dan pilih elemen 4 sebagai titik pangsi
• Periksa sama ada 1 < 4 (titik pangsi)
• Semak sama ada 6 < (titik pangsi)
• Periksa sama ada 2 < 4 (titik pangsi)
• 2 < 4 (titik pangsi) adalah benar, tukar indeks 2 dengan indeks tersimpan 6
• (titik pangsi)
• Semak jika 3 < 4 (titik pangsi)
• 3 < 4 (titik pangsi) Jika benar, simpan indeks 3 dan 6 Lakukan pertukaran
titik storan
• indeks 3
• Pada masa ini, bahagian kiri titik pangsi 4 semuanya kurang daripada 4, dan bahagian kanan lebih besar daripada 4

Tertib tatasusunan semasa ialah [3, 1, 2, 4, 9, 6].

Langkah seterusnya:

• Mula-mula susun bahagian kiri dulu
• Pilih elemen 3 sebagai titik pangsi
• Semak jika 1 <
  ;
; 3 (titik pangsi)
Tukar titik pangsi 3 dan nilai indeks storan 2
Sekarang titik pangsi telah dipecahkan pada kedudukan yang disusun
[2,1] Pilih titik 2 sebagai pangsi
• Periksa sama ada 1 < 2 (titik pangsi)
• Perjalanan di sebelah kiri selesai, dan titik pangsi 2 dan indeks storan 1 ditukar
• Begitu juga dengan bahagian kanan...elakkan visual Saya tidak akan menerangkan keletihan satu persatu, tetapi anda boleh melihat gambar demonstrasi dinamik di bawah.

2.

import java.util.Arrays;

public class QuickSortDemo {
    //四个步骤：
    //1.比较startIndex和endIndex，更喜欢理解为校验
    //2.找出基准
    //3.左边部分排序
    //4.右边排序
    public static void quickSort(int[] arr, int startIndex, int endIndex) {
        if (startIndex < endIndex) {
            //找出基准
            int partition = partition(arr, startIndex, endIndex);
            //分成两边递归进行
            quickSort(arr, startIndex, partition - 1);
            quickSort(arr, partition + 1, endIndex);
        }
    }

    //找基准
    private static int partition(int[] arr, int startIndex, int endIndex) {
        int pivot = arr[startIndex];
        
        int left = startIndex;
        int right = endIndex;
        
        //等于就没有必要排序
        while (left != right) {
            
            while (left < right && arr[right] > pivot) {
                right--;
            }
          
            while (left < right && arr[left] <= pivot) {
                left++;
            }
            //找到left比基准大，right比基准小，进行交换
            if (left < right) {
                swap(arr, left, right);
            }
        }
        //第一轮完成，让left和right重合的位置和基准交换，返回基准的位置
        swap(arr, startIndex, left);
        return left;
    }

    //两数交换
    public static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    public static void main(String[] args) {
        int[] a = {3, 1, 2, 4, 9, 6};
        quickSort(a, 0, a.length - 1);
        //输出结果
        System.out.println(Arrays.toString(a));
    }
}

Salin selepas log masuk

Hasil keluaran:

[1, 2, 3, 4, 6, 9]

Salin selepas log masuk

Pelaksanaan kod, adalah disyorkan untuk menggabungkannya dengan animasi sebelumnya untuk memudahkan pemahaman.

Terdapat beberapa cara untuk menulis jenis cepat Jika anda berminat, anda boleh melihatnya sendiri.

4. Analisis kerumitan

Kerumitan masa:

Senario terburuk ialah elemen yang diambil setiap kali ialah unsur terkecil/terbesar dalam susunan ini susunan satu elemen setiap kali)

Dalam kes ini, kerumitan masa mudah dikira, iaitu kerumitan masa isihan gelembung: T[n] = n * (n-1) = n^2 + n ;

Kes terbaik ialah O(nlog2n), proses terbitan adalah seperti berikut:

(formula kerumitan masa algoritma rekursif: T[n] = aT[n/b] + f(n) )

https://img2018.cnblogs.com/blog/1258817/201903/1258817-20190326191158640-601403776.png

Jadi kerumitan masa purata

Kerumitan ruang:

Ruang digunakan oleh isihan pantas ialah O(1), iaitu tahap malar; dan apa yang benar-benar menggunakan ruang ialah panggilan rekursif, kerana setiap ulangan mesti mengekalkan beberapa data:

Dalam kes optimum, kerumitan ruang ialah: O(log2n ); Apabila kumpulan dibahagikan sama setiap masa

Kerumitan ruang kes terburuk ialah: O(n); Ia merosot ke dalam kes jenis gelembung

Jadi kerumitan ruang purata ialah O (log2n)

5. Ringkasan kaedah pengisihan pantas

• Elemen pertama diambil sebagai titik pangsi secara lalai (pengesahan titik pangsi membezakan antara "kaedah pengisihan cepat" dan "kaedah pengisihan rawak") Dua algoritma, manakala pengisihan rawak secara rawak menandakan elemen sebagai titik pangsi;
• Jika dua elemen bukan bersebelahan ditukar, berbilang pesanan terbalik boleh dihapuskan dengan satu pertukaran, mempercepatkan proses pengisihan.

Postskrip

Akhir sekali, adakah anda rasa quick sort berguna di tempat kerja? Saya tidak pernah menggunakannya selepas bekerja selama hampir sepuluh tahun, tetapi saya tahu idea beratur cepat. Jika saya tidak bersedia sebelum temuduga, saya pasti tidak akan dapat menulisnya pula.