Bách khoa toàn thư cởi Wikipedia
Phân loại | Giải thuật chuẩn bị xếp |
---|---|
Cấu trúc dữ liệu | Ngẫu nhiên |
Hiệu suất tình huống tệ nhất | Trung bình |
Độ phức tạp không khí tình huống tệ nhất | Không tốn tăng vùng nhớ |
Tối ưu | Không |
Sắp xếp nổi bọt (tiếng Anh: bubble sort) là 1 trong thuật toán bố trí đơn giản và giản dị, với thao tác cơ phiên bản là đối chiếu nhị thành phần kề nhau, nếu như bọn chúng ko đứng đích thị trật tự thì thay đổi điểm (swap). cũng có thể tổ chức kể từ bên trên xuống (bên trái ngược sang) hoặc kể từ bên dưới lên (bên cần sang). Sắp xếp nổi bọt còn mang tên là sắp xếp vày đối chiếu trực tiếp. Nó dùng luật lệ đối chiếu những thành phần nên là 1 trong giải thuật bố trí loại đối chiếu.
Bạn đang xem: thuật toán sắp xếp nổi bọt
Giải thuật[sửa | sửa mã nguồn]
Sắp xếp kể từ bên trên xuống[sửa | sửa mã nguồn]
Giả sử mặt hàng cần thiết bố trí với n thành phần. Khi tổ chức kể từ bên trên xuống, tao đối chiếu nhị thành phần đầu, nếu như thành phần đứng trước to hơn thành phần đứng sau thì thay đổi điểm bọn chúng lẫn nhau. Tiếp tục thực hiện vì vậy với cặp thành phần loại nhị và loại thân phụ và nối tiếp cho tới cuối tập trung tài liệu, tức là đối chiếu (và thay đổi điểm nếu như cần) thành phần loại n-1 với thành phần loại n. Sau đoạn này thành phần ở đầu cuối đó là thành phần lớn số 1 của mặt hàng.
Sau tê liệt, quay trở lại đối chiếu (và thay đổi chố nếu như cần) nhị thành phần đầu cho tới khi bắt gặp thành phần loại n-2....
Ghi chú: Nếu nhập một phiên duyệt, ko cần thay đổi điểm bất kể cặp thành phần này thì list và đã được bố trí hoàn thành.
Sắp xếp kể từ bên dưới lên[sửa | sửa mã nguồn]
Sắp xếp kể từ bên dưới lên đối chiếu (và thay đổi điểm nếu như cần) chính thức từ các việc đối chiếu cặp thành phần loại n-1 và n. Tiếp theo đòi là đối chiếu cặp thành phần loại n-2 và n-1,... cho tới khi đối chiếu và thay đổi điểm cặp thành phần loại nhất và loại nhị. Sau đoạn này thành phần nhỏ nhất và đã được nổi lên địa điểm bên trên nằm trong (nó tương tự hình hình ảnh của những "bọt" khí nhẹ nhõm rộng lớn được nổi lên trên). Tiếp theo đòi tổ chức với những thành phần kể từ thứ hai cho tới loại nm.
Mã giả[sửa | sửa mã nguồn]
Sắp xếp kể từ bên trên xuống[sửa | sửa mã nguồn]
procedure bubble_sort1(list L, number n) //n=listsize For number i from n downto 2 for number j from 1 to (i - 1) if L[j] > L[j + 1] //nếu bọn chúng ko đích thị loại tự swap(L[j], L[j + 1]) //đổi điểm bọn chúng mang đến nhau endif endfor endfor endprocedure
Sắp xếp kể từ bên dưới lên[sửa | sửa mã nguồn]
procedure bubble_sort2(list L, number n) //n=listsize For number i from 1 to n-1 for number j from n-1 downto i if L[j] > L[j + 1] //nếu bọn chúng ko đích thị loại tự swap(L[j], L[j + 1]) //đổi điểm bọn chúng mang đến nhau endif endfor endfor endprocedure
Giảm giảm sút vòng duyệt[sửa | sửa mã nguồn]
Nếu nhập một phiên duyệt này tê liệt với cùng một i cố định và thắt chặt khi vòng lặp j kết thúc giục tuy nhiên không nhất thiết phải thay đổi điểm cặp thành phần này, tức là từng cặp thành phần kề nhau đang được đứng đích thị trật tự thì mặt hàng và đã được bố trí và ko cần thiết tổ chức vòng lặp tiếp sau. Do tê liệt hoàn toàn có thể người sử dụng một cờ nhằm trấn áp việc này. Ta với một quãng mã fake của thuật toán nổi lớp bọt như sau:
procedure bubble_sort3(list L, number n) i:= n while i > 1 do has_swapped:= 0 //khởi tạo ra lại độ quý hiếm cờ for number j from 1 to (i - 1) if L[j] > L[j + 1] //nếu bọn chúng ko đích thị loại tự swap(L[j], L[j + 1]) //đổi điểm bọn chúng mang đến nhau has_swapped:= 1 //có thay đổi điểm tối thiểu một phiên, list ko bố trí xong endif endfor if has_swapped = 0 //nếu không tồn tại phiên thay đổi nơi nào, list đang được bố trí xong exit else //nếu với tối thiểu một phiên thay đổi điểm, list ko bố trí xong i = i - 1 endif enddo endprocedure
Ghi chú: Cũng hoàn toàn có thể ko nhớ dùng cho tới phát triển thành i, khi tê liệt từng phiên đánh giá đều cần duyệt từ trên đầu cho tới cuối mặt hàng.
Thời gian dối tính[sửa | sửa mã nguồn]
Với từng i = 1,2,..,n-1 tao cần thiết i luật lệ đối chiếu. Do tê liệt số tối đa những phiên đối chiếu và thay đổi điểm nhập giải thuật là
Do tê liệt chừng phức tạp của giải thuật cỡ O().
Mã thiệt ví dụ[sửa | sửa mã nguồn]
Viết vày Pascal[sửa | sửa mã nguồn]
var a: array[1..1000] of integer; n, i: integer; procedure BubbleSort; var i, j, tmp: integer; begin for i:= 1 đồ sộ n - 1 do for j:= i + 1 đồ sộ n do if a[i] < a[j] then begin tmp:= a[i]; a[i]:= a[j]; a[j]:= tmp; end; end; BEGIN readln(n); for i:= 1 đồ sộ n do readln(a[i]); BubbleSort; for i:= 1 đồ sộ n do write(a[i], ' '); readln END.
Viết vày Java[sửa | sửa mã nguồn]
private static void bubbleSort(int[] unsortedArray, int length) { int temp, counter, index; for(counter=0; counter<length-1; counter++) { //Loop once for each element in the array. for(index=0; index<length-1-counter; index++) { //Once for each element, minus the counter. if(unsortedArray[index] > unsortedArray[index+1]) { //Test if need a swap or not. temp = unsortedArray[index]; //These three lines just swap the two elements: unsortedArray[index] = unsortedArray[index+1]; unsortedArray[index+1] = temp; } } } }
Viết vày C++[sửa | sửa mã nguồn]
#include <bits/stdc++.h> using namespace std; long long a[N], n;//Thay N là số thành phần nhập mảng template<class T,class Cmp = less<T> > void bubblesort(T *L,T *R,Cmp ss= less<T>()) //sap *L,*(L+1)...*(R-1) { for(T *i=L;i<R;i++) for(T *j=R-1;j>L;j--) if(ss(*j,*(j-1))) swap(*j,*(j-1)); } int main() { cin>>n; for(int i=1; i<=n;i++) cin>>a[i]; bubblesort(a+1,a+n+1); for(int i=1; i<=n;i++) cout<<a[i]<<" "; }
Viết vày PHP[sửa | sửa mã nguồn]
$arr=array(1,5,7,8,9,10,2,3,6); function s($a,$b){ if($a==$b){ return 1; } if($a<$b){ return 1; }else{ return -1; } } usort($arr,'s'); print_r($arr); exit(); other code $arr = [...]; $arr_count = count($arr); //loop for ($i = 0; $i < $arr_count; $i++) { for ($j = 1; $j < $arr_count - $i; $j++) { if ($arr[$j-1] > $arr[$j]) { $tmp = $arr[$j-1]; $arr[$j-1] = $arr[$j]; $arr[$j] = $tmp; } } } for($i=0;$i<$arr_count;$i++){ echo $arr[$i]."<br>"; }
Viết vày Python[sửa | sửa mã nguồn]
list = [] list_final = [] num = int(input("how many number you want đồ sộ add?\n")) for i in range(num) : number = int(input("adding numbers")) list.append(number) if list[i] not in list_final : list_final.append(list[i])#if list exits the same number many timnes , it will delete and make the list_final for j in range(len(list_final)): for k in range(j): if list_final[j] < list_final[k]:#compare numbers in the list tmp = list_final[j] list_final[j] = list_final[k] list_final[k] = tmp print(list_final)
Xem thêm[sửa | sửa mã nguồn]
- Sắp xếp chèn
- Sắp xếp chọn
- Sắp xếp vun đống
- Sắp xếp nhanh
- Sắp xếp trộn