Cara melaksanakan isihan sisipan dan isihan Bukit dalam struktur data Java

1. Teks

1. Konsep pengisihan dan aplikasinya

1.1 Konsep pengisihan

Isih: Apa yang dipanggil pengisihan ialah operasi menyusun rentetan rekod dalam susunan bertambah atau berkurang mengikut saiz satu atau beberapa kata kunci di dalamnya.

Kestabilan: Andaikan terdapat berbilang rekod dengan kata kunci yang sama dalam urutan rekod yang akan diisih, susunan relatif rekod ini kekal tidak berubah, iaitu, dalam asal Dalam jujukan, r[i]=r[j], dan r[i] sebelum r[j], dan dalam jujukan yang diisih, r[i] masih sebelum r[j], ia dipanggil pengisihan ini An algoritma adalah stabil; jika tidak, ia dikatakan tidak stabil.

Isih dalaman: Isih di mana semua elemen data diletakkan dalam ingatan.

Isih luaran: Terdapat terlalu banyak elemen data yang tidak boleh diletakkan dalam memori pada masa yang sama Mengikut keperluan proses pengisihan, data tidak boleh dialihkan antara dalaman dan ingatan luaran.

1.2 Aplikasi pengisihan

Selepas membaca konsep asas pengisihan, sesetengah rakan mungkin bertanya, walaupun saya belajar menyusun, adakah ia berguna dalam kehidupan sebenar? ? Sebenarnya Pengisihan ada di mana-mana dalam kehidupan , seperti pemilihan dimensi produk yang berbeza, atau kedudukan universiti Malah, ada idea untuk menyusunnya Belajar susun dengan baik, dan anda boleh Bantu kami memerhati semua aspek kehidupan dari dimensi lain dan bantu kami menyelesaikan masalah dalam kehidupan dengan lebih baik .

1.3 Algoritma pengisihan biasa

Dalam bidang struktur data, kami biasa Terdapat empat algoritma pengisihan:

①Isih sisipan: isihan sisipan langsung, isihan bukit

②Isih pilihan: isihan pilihan, isihan timbunan

③Isih pertukaran: isihan gelembung, isih cepat

④Isih gabung: isihan gabung

2 . Pelaksanaan algoritma isihan sisipan

Disebabkan kekangan ruang, dalam artikel ini kami terutamanya memperkenalkan isihan sisipan langsung dan Isih bukit dalam jenis sisipan , dan jenis sisipan terus sering dipanggil jenis sisipan.

2.1 Isih sisipan

2.1.1 Idea asas

Isih sisipan terus ialah kaedah isihan sisipan yang mudah

Asasnya idea adalah untuk memasukkan rekod untuk diisih ke dalam urutan tersusun yang telah diisih satu demi satu mengikut saiz nilai utamanya, sehingga semua rekod dimasukkan dan urutan tertib baharu diperoleh

 Malah, apabila kita bermain poker, kita menggunakan idea jenis sisipan. Apabila anda melukis kad baharu, anda secara semula jadi akan membandingkannya dengan longgokan kad sedia ada di tangan anda satu demi satu, dan kemudian meletakkannya di tempat yang sepatutnya selepas perbandingan. Jadi kita mungkin tidak tahu apa itu jenis sisipan, tetapi pendekatan bawah sedar kita betul-betul selaras dengan jenis sisipan.

2.1.2 Isih sisipan langsung

Gunakan bahasa yang lebih bertulis untuk menerangkan isihan sisipan langsung: Apabila memasukkan unsur ke-i (i>=1), sebelumnya Tatasusunan[0],tatasusunan[1],...,tatasusunan[i-1] telah diisih Pada masa ini, gunakan kod pengisihan tatasusunan[i] dan tatasusunan[i-1],tatasusunan[i -2], …Bandingkan susunan kod pengisihan, cari kedudukan sisipan dan tatasusunan sisipan[i]. , jadi mari kita letakkannya dalam istilah orang biasa Mari kita bincang. Kini

terdapat susunan tidak teratur di hadapan anda Tujuan kami adalah untuk melaraskan tatasusunan tidak teratur ini kepada susunan menaik atau menurun

. Mengambil tertib menaik sebagai contoh, memandangkan tatasusunan tidak tertib, kita perlu

mula mengisih

daripada elemen kedua tatasusunan. Mengapa tidak yang pertama? Kerana apabila hanya ada satu nombor, anda tidak boleh membandingkannya dengan unsur-unsur lain Sememangnya, tidak ada perkara seperti gangguan Oleh itu, apabila hanya ada satu unsur, kita lalai untuk memerintahkannya.

Selepas memahami mengapa kita perlu mengisih daripada elemen kedua, kini kita perlu memasukkan dan mengisih elemen mengikut urutan . Yang pertama ialah sisipan dan pengisihan elemen kedua Dalam gambar di bawah, kita akan dapati elemen kedua ialah 44. 44 lebih besar daripada elemen pertama sebanyak 3, jadi tidak perlu memindahkan elemen kedua. Seterusnya ialah memasukkan dan menyusun elemen ketiga Kami mendapati bahawa elemen ketiga 38 adalah lebih kecil daripada elemen kedua 44, yang tidak memenuhi jangkaan kami untuk tertib menaik Oleh itu, kami bergerak 44 ke kedudukan 38. Antara yang kedua dan elemen ketiga, Selepas menyusun, kami mendapati bahawa 38 adalah lebih besar daripada 3, iaitu, elemen pertama dan kedua juga dalam susunan, jadi tidak perlu memindahkan kedudukan elemen pertama Pada masa ini, kami telah mengesahkan bahawa 38 sepatutnya berada dalam elemen kedua dalam elemen, jadi kami hanya memasukkan 38 ke dalam kedudukan elemen kedua. Saya percaya bahawa rakan-rakan yang telah melihat ini sepatutnya dapat memasukkan dan mengisih elemen berikutnya dengan mudah

Langkah seterusnya ialah menulis kod . Dari segi kod, bagaimanakah kita boleh melaksanakan penyisipan dan pengisihan elemen di atas? Kami mengambil dua pembolehubah utama "des" dan "end" ialah subskrip awal elemen yang ingin kami sisipkan, dan hujung mewakili urutan sebelum sisipan elemen terakhir, dengan perbandingan des, akhir akan terus bergerak ke hadapan, jadi bilakah pergerakan hujung akan berhenti, iaitu akhir perbandingan, yang boleh dibahagikan secara kasar kepada dua situasi : ①Elemen diwakili oleh des adalah lebih besar daripada elemen yang diwakili oleh akhir ②akhir telah mencapai unsur pertama jujukan Pada masa ini, des adalah sama ada unsur pertama atau unsur kedua.

Gambar dan kod khusus adalah seperti berikut:

//插入排序[升序]
int* InsertSort(int* arr, int n)
{
 
	//整体排序
	for (int i = 1; i < n; i++)
	{
		int end = i - 1;
		int des = arr[i];
		//单趟排序
		while (end >= 0)
		{
			if (des >= arr[end])
				break;
			if (des < arr[end])
			{
				arr[end + 1] = arr[end];
				end--;
			}
			arr[end+1] = des;
		}
	}
}

Nota:

dimasukkan terus Ringkasan ciri pengisihan

①Semakin dekat set elemen untuk dipesan, semakin tinggi kecekapan masa algoritma isihan sisipan langsung

②Kerumitan masa: O(N^ 2)

③ Kerumitan ruang: O(1), ia ialah algoritma pengisihan yang stabil

④ Kestabilan: stabil

2.1.3 Pengisihan bukit (kenaikan mengecut Pengisihan)

Kaedah pengisihan bukit juga dipanggil kaedah kenaikan mengecut.

Idea asas kaedah pengisihan Bukit ialah: mula-mula pilih integer, bahagikan semua rekod dalam fail untuk diisih ke dalam kumpulan integer, letakkan semua rekod dengan jarak Rekod diisih. Kemudian ulangi kerja pengumpulan dan pengisihan di atas Apabila integer sama dengan 1, semua rekod diisih dalam kumpulan yang sama.

Secara umumnya,

Isih bukit ialah pengisihan sisipan langsung berbilang, tetapi pengisihan kecuali untuk pengisihan sisipan langsung yang terakhir adalah berbeza daripada pengisihan sisipan langsung yang asal. Oleh itu, apabila sesetengah rakan melihat ini, mereka mungkin bertanya mengapa jenis sisipan berbilang dilakukan. Apakah perbezaan antara jenis sisipan tunggal dan jenis sisipan biasa? Jangan risau, kami akan menjawabnya satu persatu di bawah.

Pertama, mengapa anda perlu memasukkan isihan beberapa kali Selepas membaca ringkasan ciri-ciri isihan sisipan di atas, kita akan mendapati bahawa

Apabila set elemen lebih hampir kepada susunan, kecekapan masa? pengisihan sisipan akan menjadi Semakin tinggi . Oleh itu, tujuan pengisihan Bukit, kecuali pengisihan terakhir ialah pengisihan sisipan biasa, adalah untuk sentiasa melaraskan set elemen supaya sentiasa hampir dengan pesanan .

Langkah seterusnya ialah perbezaan antara pengisihan Bukit dan pengisihan sisipan biasa kecuali untuk pengisihan sisipan yang terakhir. Melalui kajian jenis sisipan di atas, kita akan mendapati bahawa untuk tatasusunan yang tidak teratur, jika sesuatu elemen ingin mencapai kedudukan yang betul, ia mesti dibandingkan dengan elemen lain satu demi satu, iaitu, bergerak selangkah demi selangkah Ini tidak mengapa apabila bilangan elemen dalam tatasusunan adalah kecil, tetapi apabila bilangan elemen dalam tatasusunan adalah besar, dalam tertib menaik, bayangkan bahawa elemen terbesar dalam tatasusunan terletak pada kedudukan pertama tatasusunan, maka ialah ia perlu untuk Elemen ini boleh mencapai kedudukan terakhir tatasusunan hanya selepas membandingkannya satu demi satu dengan elemen lain dalam tatasusunan Walau bagaimanapun, apabila kita

meningkatkan kadar perbandingan, iaitu, meningkatkan jarak antara dua elemen yang dibandingkan, maka ini Bolehkah elemen itu sampai ke tempat yang sepatutnya . Letakkan dalam situasi catur terbang, lontaran isihan sisipan 1 setiap kali, dan isihan cincang kecuali isihan sisipan terakhir melontar mata 1, lontaran isihan sisipan yang selebihnya semuanya lebih besar daripada 1. , jadi boleh dibayangkan bahawa pengisihan cincang boleh mencapai penghujung pengisihan dengan lebih cepat.

Untuk memudahkan pemahaman rakan, bahagian kod ini dibahagikan kepada dua bahagian: ① isihan sisipan terus langkah tetap ② isihan cincang.

先是固定步伐的直接插入排序，先让我们通过图片来直观的看到数组数组内的元素通过这种操作后的变化。

//固定步伐的直接插入排序[升序]
void ShellSort(int* arr, int n)
{
	int gap = 3;
	int end;
	//有两种写法，看你要控制end，还是des
	/*for (int i=0; i < n-gap; i++)
	{
		int end = i;
		int des = arr[end + gap];
		while (end >= 0)
		{
			if (des >= arr[end])
				break;
			if (des < arr[end])
			{
				arr[end + gap] = arr[end];
				end -= gap;
			}
			arr[end + gap] = des;
		}
	}*/
 
	for (int i = gap; i < n ; i++)
	{
		int end = i-gap;
		int des = arr[end + gap];
		while (end >= 0)
		{
			if (des >= arr[end])
				break;
			if (des < arr[end])
			{
				arr[end + gap] = arr[end];
				end -= gap;
			}
			arr[end + gap] = des;
		}
	}
}

接着就是希尔排序

上述的代码是gap=3的情况下的直接插入排序，那么对于希尔排序而言，我们该对gap该如何选择呢？对于不同gap值的插入排序来说，我们会发现：gap越大，元素跳得越快，数组越不接近有序；而gap越小，元素跳的越慢，数组越接近有序。由于数组的大小不定，因此希尔排序也没有一个合适gap值适用于所有数组，显然，这个gap值一定是动态变化的。

对于gap的动态变化，常见的有两种：

①令gap等于数组的元素个数，每次插入排序后令gap除等2

②另一种则是令gap等于数组的元素个数，不过每次插入排序后令gap除以3再加1

无论哪种处理都能使gap动态变化并最后等于1，对数组进行一次插入排序，达到最后想要的效果。

代码如下：

//希尔排序
void ShellSortPlus(int* arr, int n)
{
	int gap=n;
	int end;
	while (gap > 1)
	{
	gap = gap / 2;
		
		for (int i=0; i < n - gap;i++)//有两种写法，看你要控制end，还是des
		{
			int end = i;
			int des = arr[end + gap];
			while (end >= 0)
			{
				if (des >= arr[end])
					break;
				if (des < arr[end])
				{
					arr[end + gap] = arr[end];
					end -= gap;
				}
				arr[end + gap] = des;
			}
		}
 
	}
}

二、测试代码

为了方便小伙伴们测试排序后的效果，为大家提供了测试的代码并包含排序的具体代码和包含的头文件。

#include 
#include 
#include 
 
//插入排序[升序]
int* InsertSort(int* arr, int n)
{
 
	//整体排序
	for (int i = 1; i < n; i++)
	{
		int end = i - 1;
		int des = arr[i];
		//单趟排序
		while (end >= 0)
		{
			if (des >= arr[end])
				break;
			if (des < arr[end])
			{
				arr[end + 1] = arr[end];
				end--;
			}
			arr[end+1] = des;
		}
	}
}
 
//固定步伐的直接插入排序[升序]
void ShellSort(int* arr, int n)
{
	int gap = 3;
	int end;
	//有两种写法，看你要控制end，还是des
	/*for (int i=0; i < n-gap; i++)
	{
		int end = i;
		int des = arr[end + gap];
		while (end >= 0)
		{
			if (des >= arr[end])
				break;
			if (des < arr[end])
			{
				arr[end + gap] = arr[end];
				end -= gap;
			}
			arr[end + gap] = des;
		}
	}*/
 
	for (int i = gap; i < n ; i++)
	{
		int end = i-gap;
		int des = arr[end + gap];
		while (end >= 0)
		{
			if (des >= arr[end])
				break;
			if (des < arr[end])
			{
				arr[end + gap] = arr[end];
				end -= gap;
			}
			arr[end + gap] = des;
		}
	}
}
 
 
//希尔排序
void ShellSortPlus(int* arr, int n)
{
	int gap=n;
	int end;
	while (gap > 1)
	{
	gap = gap / 2;
		
		for (int i=0; i < n - gap;i++)//有两种写法，看你要控制end，还是des
		{
			int end = i;
			int des = arr[end + gap];
			while (end >= 0)
			{
				if (des >= arr[end])
					break;
				if (des < arr[end])
				{
					arr[end + gap] = arr[end];
					end -= gap;
				}
				arr[end + gap] = des;
			}
		}
 
	}
}
 
//打印排序好的数组
void PrintSort(int*arr,int n)
{
	for(int i=0;i
Salin selepas log masuk

Atas ialah kandungan terperinci Cara melaksanakan isihan sisipan dan isihan Bukit dalam struktur data Java. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!