>> MARK GROZEN-SMITH: Xin chào, tôi Đánh Grozen-Smith, và đây là Sắp xếp nhanh.
Cũng giống như sắp xếp chèn và bong bóng sắp xếp, Sắp xếp nhanh là một thuật toán cho
sắp xếp một danh sách hoặc một mảng của sự vật.
Để đơn giản, chúng ta hãy giả sử rằng những mọi thứ chỉ là số nguyên, nhưng
biết rằng Sắp xếp nhanh làm việc cho hơn chỉ số.
QuickStart là phức tạp hơn một chút hơn chèn hoặc bong bóng, nhưng nó
cũng hiệu quả hơn trong nhiều trường hợp.
Chờ đợi một giây.
Anh ta chỉ cần nói "nhất trường hợp, "không phải là" tất cả "?
Điều thú vị là không có.
Không phải tất cả các trường hợp là như nhau.
Đừng lo lắng về chi tiết này nếu bạn không nhìn thấy ký hiệu O lớn, nhưng
Sắp xếp nhanh là một O (n bình phương) thuật toán lúc tồi tệ nhất, giống như
chèn hay bong bóng sắp xếp.
Tuy nhiên, nó thường hoạt động nhiều hơn nữa như một thuật toán m tương tự cũ.
Tại sao?
Chúng tôi sẽ lấy lại cho rằng sau này.
Nhưng bây giờ, chúng ta hãy tìm hiểu Sắp xếp nhanh như thế nào hoạt động.
>> Vì vậy, hãy đi bộ qua Quicksorting này mảng các số nguyên từ nhỏ nhất
để lớn nhất.
Ở đây chúng tôi có các số nguyên 6, 5, 1, 3, 8, 4, 7, 9, và 2.
Đầu tiên, chúng ta chọn các yếu tố cuối cùng của mảng này - trong trường hợp này, hai -
và gọi đó là "trục". Tiếp theo, chúng tôi bắt đầu nhìn vào hai điều -
một, chỉ số thấp nhất, mà tôi sẽ tham khảo là ở bên phải của
tường, và, hai, tận cùng bên trái yếu tố, mà tôi sẽ gọi là "hiện tại
yếu tố. "Những gì chúng tôi sẽ làm là xem xét tất cả các yếu tố khác, khác
so với trục, và đặt tất cả các yếu tố nhỏ hơn pivot đến
bên trái của bức tường và tất cả những lớn hơn pivot đến
phải bức tường.
Sau đó, cuối cùng, chúng tôi sẽ thả các trục ngay trên bức tường để đặt nó giữa
tất cả các số nhỏ hơn nó và tất cả các số lớn hơn.
>> Vì vậy, hãy làm điều đó.
Lấy 2, đặt tường ở bắt đầu, và gọi 6 "hiện tại
yếu tố. "Vì vậy, chúng tôi muốn xem xét phần tử hiện tại của chúng tôi, 6.
Và kể từ khi nó lớn hơn 2, chúng ta để nó ở đó cho
phải bức tường.
Sau đó, chúng tôi chuyển sang nhìn vào 5 như của chúng tôi phần tử hiện tại và thấy rằng điều này
là, một lần nữa, lớn hơn so với trục, vì vậy chúng tôi để ở những nơi nó ở bên phải
bên của bức tường.
Chúng tôi di chuyển trên.
Phần tử hiện tại của chúng tôi là bây giờ 1, và - oh.
Điều này khác với bây giờ.
Các yếu tố hiện tại là nhỏ hơn trục, vì vậy chúng tôi muốn đặt nó
bên trái của bức tường.
Để làm điều này, chúng ta hãy chuyển đổi phần tử hiện tại với chỉ số thấp nhất
ngồi ngay bên phải của bức tường.
Bây giờ, chúng tôi di chuyển bức tường lên một chỉ số vì vậy 1 là bên trái
bên của bức tường bây giờ.
>> Chờ đợi.
Tôi chỉ pha trộn các yếu tố trên phía bên phải của bức tường, đúng không?
Đừng lo lắng.
Đó là tốt.
Điều duy nhất chúng tôi quan tâm bây giờ là tất cả những yếu tố để các
bên phải của bức tường có kích thước lớn so với trục.
Không có thứ tự thực tế là giả định được nêu ra.
>> Bây giờ, trở lại để phân loại.
Vì vậy, chúng tôi tiếp tục nhìn phần còn lại của các yếu tố.
Và trong trường hợp này, chúng ta thấy rằng có không có các yếu tố khác ít hơn
trục, vì vậy chúng tôi để lại cho họ tất cả các ngày phía bên phải của bức tường.
Cuối cùng, chúng tôi đến được với các yếu tố hiện tại và thấy rằng nó là trục.
Bây giờ, điều đó có nghĩa rằng chúng tôi có hai phần của mảng, đầu tiên là
nhỏ trên trục và ở phía bên trái của bức tường, và con thứ hai
lớn hơn pivot đến phía bên phải của bức tường.
Chúng tôi muốn đưa các yếu tố trục giữa hai, và sau đó chúng ta sẽ biết
rằng pivot là ở bên phải của nó thức nơi được sắp xếp.
Vì vậy, chúng tôi chuyển đổi phần tử đầu tiên trên phía bên phải của bức tường với các trục,
và chúng ta biết của trục trong đúng vị trí của nó.
>> Sau đó chúng ta lặp lại quá trình này cho các subarrays trái và bên phải của trục.
Kể từ khi mảng con cuối cùng là chỉ có một yếu tố dài, chúng tôi biết đó là đã có
sắp xếp bởi làm sao bạn có thể được ra khỏi đặt hàng nếu bạn chỉ có một phần tử?
Cho phía bên phải của mảng con, chúng tôi thấy rằng trục là 5, và tường
chỉ là bên trái của 6.
Và các yếu tố hiện tại cũng bắt đầu ra như là 6.
Vì vậy, 6 là lớn hơn 5.
Chúng tôi để ở những nơi đó là trên phía bên phải của bức tường.
Bây giờ, di chuyển trên, 3 dưới 5.
Vì vậy, chúng tôi chuyển đổi nó với phần tử đầu tiên vừa phải của bức tường.
Bây giờ, tôi chuyển bức tường lên một.
Bây giờ, chuyển sang 8.
8 lớn hơn 5, và vì vậy chúng tôi rời khỏi nó.
4 nhỏ hơn 5, vì vậy chúng tôi chuyển đổi nó.
Và trên.
>> Mỗi lần chúng ta lặp lại quá trình trên bên trái và bên phải của mảng. chúng tôi
chọn một trục và làm so sánh và tạo ra một mức độ trái và
subarrays ngay.
Gọi đệ quy này sẽ tiếp tục cho đến khi chúng tôi đạt được kết thúc khi chúng tôi đã
phân chia các mảng tổng thể vào chỉ subarrays chiều dài 1.
Từ đó, chúng ta biết mảng được sắp xếp bởi vì mỗi yếu tố có, tại
một số điểm, là một trục.
Nói cách khác, cho mỗi yếu tố, tất cả các con số bên trái là ít hơn
giá trị và tất cả các con số để các ngay có giá trị lớn hơn.
>> Phương pháp này hoạt động rất tốt nếu giá trị của trục được lựa chọn là
khoảng ở giữa phạm vi của các giá trị danh sách.
Điều này có nghĩa rằng, sau khi chúng tôi di chuyển các yếu tố xung quanh, có khoảng bao nhiêu
các yếu tố bên trái của trục như có bên phải.
Và tính chất chia-và-chinh phục của Thuật toán Sắp xếp nhanh sau đó được đưa
tận dụng tối đa.
Điều này tạo ra một thời gian chạy của O (n log n,) n vì chúng ta phải làm n trừ đi 1
so sánh trên mỗi thế hệ và đăng nhập n vì chúng ta phải phân chia danh sách
log n lần.
Tuy nhiên, trong trường hợp xấu nhất, điều này thuật toán thực sự có thể là O (n
bình phương.) Giả sử trên mỗi thế hệ, trục chỉ để xảy ra là
nhỏ nhất hoặc lớn nhất của số chúng tôi đang phân loại.
Điều này có nghĩa phá vỡ danh sách n lần và ra n trừ đi 1
so sánh mỗi lần duy nhất.
Vì vậy, o n bình phương.
>> Làm thế nào chúng ta có thể cải thiện phương pháp?
Một cách tốt để cải thiện phương pháp này là cắt giảm xác suất mà
thời gian chạy là bao giờ thực sự o n bình phương.
Nhớ tồi tệ nhất kịch bản này, trường hợp xấu nhất chỉ có thể xảy ra khi
trục lựa chọn luôn luôn là cao nhất hoặc giá trị thấp nhất trong mảng.
Để đảm bảo điều này ít có khả năng xảy ra, chúng ta có thể tìm thấy những trục bằng
lựa chọn nhiều yếu tố và lấy giá trị trung bình.
>> Tên tôi là Mark Grozen-Smith, và đây là CS50.
>> Để đơn giản, chúng ta hãy giả sử rằng những mọi thứ chỉ là số nguyên, nhưng
biết rằng Quicksert -
Quicksert?
Xin lôi.
>> Ở đây chúng tôi có các số nguyên 6, 5, 1, 3, 8, 4, 9.
>> SPEAKER 1: Thật sao?
>> SPEAKER 2: Không dừng lại ở đó.
>> SPEAKER 1: Thật sao?