Komik: Kabarcık sıralaması nedir?
----- O sabah -----
Kabarcık sıralama nedir?
İngilizce Bubble Sort, Bubble Sort, en temel değişim sıralamasıdır.
Herkes gazoz içmiş olmalı, gazlı içeceklerde genellikle tepeye kadar yüzen çok sayıda küçük kabarcık vardır. Bunun nedeni, küçük baloncukları oluşturan karbondioksitin sudan daha hafif olmasıdır, bu nedenle küçük kabarcıklar yavaş yavaş yukarı doğru yüzebilir.
Kabarcık sıralamamızın kabarcık sıralama olarak adlandırılmasının nedeni, bu sıralama algoritmasının her bir öğesinin, kendi boyutuna göre dizinin bir tarafına doğru azar azar hareket eden küçük bir balon gibi olabilmesidir.
Nasıl hareket ettirilir? Bir kestaneye bakalım:
Sırasız bir sıra oluşturmak için 8 sayı vardır: 5, 8, 6, 3, 9, 2, 1, 7 ve küçükten büyüğe sıralamayı umuyoruz. Kabarcıklanma sıralama fikrine göre, bitişik elemanları çiftler halinde karşılaştırmalı ve boyutlarına göre elemanların konumlarını değiştirmeliyiz. Süreç şu şekildedir:
Önce 5 ile 8'i karşılaştırın ve 5'in 8'den küçük olduğunu bulun, böylece eleman konumu değişmez.
Sonra, 8'i 6 ile karşılaştırın ve 8'in 6'dan daha büyük olduğunu bulun, böylece 8 ve 6 pozisyonları değiştirin.
8 ve 3'ü karşılaştırmaya devam edin ve 8'in 3'ten büyük olduğunu bulun, böylece 8 ve 3 konum değiştirir.
8 ve 9'u karşılaştırmaya devam edin ve 8'in 9'dan küçük olduğunu bulun, böylece eleman konumu değişmeden kalır.
Sonra, 9 ve 2'yi karşılaştırın ve 9'un 2'den büyük olduğunu bulun, bu nedenle 9 ve 2 konumlarını değiştirin.
Sonra, 9 ve 1'i karşılaştırın ve 9'un 1'den büyük olduğunu bulun, bu nedenle 9 ve 1 konumlarını değiştirin.
Son olarak, 9 ile 7'yi karşılaştırın ve 9'un 7'den büyük olduğunu bulun, böylece 9 ve 7 pozisyonları değiştirin.
Bu şekilde, dizideki en büyük öğe olan öğe 9, bir sodadaki küçük bir balon gibi yüzer ve en sağa doğru yüzer.
Şu anda, kabarcık sıralamamızın ilk turu sona erdi. Dizinin en sağ tarafındaki eleman 9, şu anda sadece bir elemana sahip olan sıralı bir bölge olarak kabul edilebilir.
Şimdi, ikinci sınıflandırma turunu gerçekleştirelim:
Önce 5 ile 6'yı karşılaştırın ve 5'in 6'dan küçük olduğunu bulun, böylece eleman konumu değişmeden kalır.
Sonra, 6 ile 3'ü karşılaştırın ve 6'nın 3'ten büyük olduğunu bulun, yani 6 ve 3 pozisyonları değiştirin.
6 ve 8'i karşılaştırmaya devam edin ve 6'nın 8'den küçük olduğunu bulun, böylece eleman konumu değişmeden kalır.
Sonra, 8 ve 2'yi karşılaştırın ve 8'in 2'den büyük olduğunu bulun, böylece 8 ve 2 pozisyonları değiştirin.
Sonra, 8'i 1 ile karşılaştırın ve 8'in 1'den büyük olduğunu bulun, böylece 8 ve 1 pozisyonları değiştirin.
8 ve 7'yi karşılaştırmaya devam edin ve 8'in 7'den büyük olduğunu bulun, böylece 8 ve 7 pozisyonları değiştirin.
İkinci sıralama turundan sonra, dizimizin sağ tarafındaki sıralı alan aşağıdaki sırada iki öğeye sahiptir:
Sonraki değişimlerin ayrıntılarına gelince, burada ayrıntılı olarak açıklamayacağız. Üçüncü turdan sonraki durum aşağıdaki gibidir:
Dördüncü turdan sonraki durum şu şekildedir:
Beşinci turdan sonraki durum aşağıdaki gibidir:
Altıncı turdan sonraki durum aşağıdaki gibidir:
Yedinci turdan sonraki durum aşağıdaki gibidir (zaten sıralıdır, bu nedenle değişiklik yoktur):
Sekizinci turdan sonraki durum aşağıdaki gibidir (aynısı değişmeden kalır):
Şimdiye kadar, tüm öğeler sıralı. Bu, genel kabarcık sıralama fikri.
Orijinal kabarcıklı sıralama, kararlı türdür. Sıralama algoritmasının her turunun tüm öğeleri geçmesi gerektiğinden, tur sayısı öğelerin sayısına eşittir, dolayısıyla zaman karmaşıklığı O (N ^ 2) olur.
Kabarcık sıralama kodu ve optimizasyonu
Bubble Sort'un ilk sürümü:
public class BubbleSort {
özel statik geçersiz sıralama (int dizisi)
{
int tmp = 0;
for (int i = 0; i < dizi.length; i ++) {
for (int j = 0; j < dizi.length-i-1; j ++)
{
eğer (dizi > dizi)
{
tmp = dizi;
dizi = dizi;
dizi = tmp;
}
}
}
}
public static void main (String args) {
int dizi = yeni int {5,8,6,3,9,2,1,7};
sıralama (dizi);
System.out.println (Arrays.toString (dizi));
}
}
Kod, sıralamak için çift döngü kullanarak çok basittir. Dış döngü tüm turları kontrol eder ve iç döngü, köpürme işleminin her turunu temsil eder.Önce öğeler karşılaştırılır ve ardından öğeler değiştirilir.
Orijinal balon sıralamanın optimizasyon noktaları nelerdir?
Örnek olarak 5, 8, 6, 3, 9, 2, 1, 7 dizisini alarak az önce açıklanan sıralama ayrıntılarını gözden geçirelim. Sıralama algoritması altıncı, yedinci ve sekizinci turlara uygulandığında, Sıranın durumu aşağıdaki gibidir:
Açıkça görülebilir ki, altıncı sıralama turundan bu yana, tüm dizilim zaten sıralıdır. Ancak sıralama algoritmamız yedinci ve sekizinci turları "bilinçli bir şekilde" yürütmeye devam ediyor.
Bu durumda dizinin zaten sıralı olduğunu belirleyip işaretleyebilirsek, kalan sıralama turları elenebilir ve iş erken bitirilebilir.
Bubble Sort Second Edition
public class BubbleSort {
özel statik geçersiz sıralama (int dizisi)
{
int tmp = 0;
for (int i = 0; i < dizi.length; i ++)
{
// Sıralı işaret, her turun baş harfi doğrudur
boolean isSorted = true;
for (int j = 0; j < dizi.length-i-1; j ++)
{
eğer (dizi > dizi)
{
tmp = dizi;
dizi = dizi;
dizi = tmp;
// Eleman değişimi var, bu yüzden sıralı değil ve bayrak yanlış oluyor
isSorted = false;
}
}
if (sıralı) {
kırmak;
}
}
}
public static void main (String args) {
int dizi = yeni int {5,8,6,3,9,2,1,7};
sıralama (dizi);
System.out.println (Arrays.toString (dizi));
}
}
Kodun bu sürümü, boole değişkeni isSorted'ı bir işaretçi olarak kullanarak küçük bir değişiklik yaptı. Bu sıralama turunda, elemanlar değiştiriliyorsa, bu, dizinin sıra dışı olduğu anlamına gelir; eleman değişimi yoksa, bu, dizinin zaten düzenlendiği ve doğrudan büyük döngüden atladığı anlamına gelir.
Sorunu açıklamak için bu sefer yeni bir dizi bulalım:
Bu dizinin özelliği, ilk yarının (3, 4, 2, 1) düzensiz olması, ikinci yarının (5, 6, 7, 8) artan sırada olması ve ikinci yarıdaki elemanların zaten dizinin maksimum değeri olmasıdır.
Köpüren sıralama fikrine göre sıralayalım ve belirli etkilere bir göz atalım:
İlk tur
Öğeler 3 ve 4 karşılaştırıldığında, 3'ün 4'ten küçük olduğu, dolayısıyla konumun değişmediği bulunmuştur.
Öğe 4, 2 ile karşılaştırılır ve 4'ün 2'den büyük olduğu bulunur, bu nedenle 4 ve 2 değiştirilir.
4. eleman 1 ile karşılaştırılır ve 4'ün 1'den büyük olduğu bulunur, bu yüzden 4 ve 1 değiştirilir.
Öğe 4 ve 5 karşılaştırıldığında, 4'ün 5'ten küçük olduğu, dolayısıyla konum değişmeden kaldığı bulunmuştur.
Eleman 5, 6 ile karşılaştırılır ve 5'in 6'dan küçük olduğu bulunur, bu nedenle konum değişmeden kalır.
Eleman 6 ve 7'yi karşılaştırdığımızda, 6'nın 7'den küçük olduğu bulundu, bu yüzden konum değişmeden kaldı.
Eleman 7, 8 ile karşılaştırılır ve 7'nin 8'den küçük olduğu bulunur, bu nedenle konum değişmeden kalır.
İlk turun sonunda, sıralama alanı bir öğe içerir:
ikinci tur
Öğe 3 ve 2'yi karşılaştırarak, 3'ün 2'den büyük olduğunu bulun, böylece 3 ve 2 değiştirilir.
Öğe 3, 1 ile karşılaştırılır ve 3'ün 1'den büyük olduğu bulunur, bu nedenle 3 ve 1 değiştirilir.
Öğeler 3 ve 4 karşılaştırıldığında, 3'ün 4'ten küçük olduğu, dolayısıyla konumun değişmediği bulunmuştur.
Öğe 4 ve 5 karşılaştırıldığında, 4'ün 5'ten küçük olduğu, dolayısıyla konum değişmeden kaldığı bulunmuştur.
Eleman 5, 6 ile karşılaştırılır ve 5'in 6'dan küçük olduğu bulunur, bu nedenle konum değişmeden kalır.
Eleman 6 ve 7'yi karşılaştırdığımızda, 6'nın 7'den küçük olduğu bulundu, bu yüzden konum değişmeden kaldı.
Eleman 7, 8 ile karşılaştırılır ve 7'nin 8'den küçük olduğu bulunur, bu nedenle konum değişmeden kalır.
İkinci turun sonunda, sıra alanı bir öğe içerir:
Bu sorunun kilit noktası nerede? Anahtar, dizinin sıralı alanını tanımlamaktır.
Mevcut mantığa göre, sıralı alanın uzunluğu, sıralama turlarının sayısına eşittir. Örneğin, ilk sıralama turundan sonra sıralı alanın uzunluğu 1'dir ve ikinci sıralama turundan sonra sıralı alanın uzunluğu 2 ...
Aslında, dizinin gerçek sıralı alanı bu uzunluktan daha uzun olabilir Örneğin, yalnızca ikinci turda, sonraki beş eleman aslında sıralı alana aittir. Bu nedenle, sonraki birçok öğe karşılaştırması anlamsızdır.
Bu durumdan nasıl kaçınılır? Her sıralama turunun sonunda, son eleman değişiminin konumunu kaydedebiliriz Bu konum, sırasız dizinin ve ardından sıralı alanın sınırıdır.
Bubble Sort Üçüncü Baskı
public class BubbleSort {
özel statik geçersiz sıralama (int dizisi)
{
int tmp = 0;
// Son değişimin pozisyonunu kaydedin
int lastExchangeIndex = 0;
// Sıralanmamış dizinin sınırı, her karşılaştırmanın sadece burayla karşılaştırılması gerekiyor
int sortBorder = dizi.length-1;
for (int i = 0; i < dizi.length; i ++)
{
// Sıralı işaret, her turun baş harfi doğrudur
boolean isSorted = true;
for (int j = 0; j < sortBorder; j ++)
{
eğer (dizi > dizi)
{
tmp = dizi;
dizi = dizi;
dizi = tmp;
// Eleman değişimi var, bu yüzden sıralı değil ve bayrak yanlış oluyor
isSorted = false;
// Sıralanmamış dizinin sınırını son değişim elemanının konumuna güncelle
lastExchangeIndex = j;
}
}
sortBorder = lastExchangeIndex;
if (sıralı) {
kırmak;
}
}
}
public static void main (String args) {
int dizi = yeni int {3,4,2,1,5,6,7,8};
sıralama (dizi);
System.out.println (Arrays.toString (dizi));
}
}
Kodun bu versiyonunda sortBorder, sıralanmamış dizinin sınırıdır. Her sıralama turunda sortBorder'dan sonraki öğelerin karşılaştırılmasına gerek yoktur ve sıralı olmaları gerekir.
Bu çizgi roman tamamen eğlencedir. Lütfen mevcut çalışmanıza mümkün olduğu kadar değer verin ve Xiao Hui'nin davranışını taklit etmeyin.
Yazar: küçük gri, açık anahtarlı programcı küçük gri numaraya izin verdi.
"Belgeler için arayın!"
CSDN kamu hesabı, "on milyonlarca teknik insanla büyüme" kavramını destekler. Teknik insanların ilk kez ilgilendiği endüstri odak olaylarını teknik insanların benzersiz bakış açılarından açıklamak için yalnızca "inek başlıkları" ve "konuşma" sütunlarını kullanmakla kalmaz, aynı zamanda "Teknik Başlıklar" sütunu, sektördeki popüler teknolojilerin ve uygulamaların derinlemesine bir yorumunu sunarak, tüm geliştiricilerin teknolojik trendlere ayak uydurmasına, uyanık bir teknolojik anlayışı sürdürmesine ve sektör eğilimleri ve teknolojileri hakkında daha kapsamlı bir anlayışa sahip olmasına olanak tanır.
Yüksek kaliteli makaleleriniz veya sektörün sıcak olayları, teknoloji trendleri hakkında derinlemesine bilgiler veya kapsamlı uygulama uygulamaları, senaryolarla ilgili yeni görüşler vb. Varsa, lütfen göndermek için CSDN ile iletişime geçmekten çekinmeyin. Şirket pozisyonu), e-posta (guorui@csdn.net).
