import java.util.Acak;
/**
* Menyortir kelas tes
*
* Klasifikasi algoritma pengurutan adalah sebagai berikut: 1. Penyisipan penyortiran (direct insertion sort, half insertion sort, Hill sort) 2. Exchange sort (bubble sort, quick sort);
* 3. Pengurutan seleksi (pengurutan seleksi langsung, pengurutan heap); 4. Pengurutan gabungan; 5. Pengurutan radix.
*
* Mengenai pilihan metode penyortiran: (1) Jika n kecil (misalnya n≤50), dapat digunakan penyortiran penyisipan langsung atau penyortiran pilihan langsung.
* Jika ukuran rekamannya kecil, penyortiran penyisipan langsung lebih baik; sebaliknya, karena jumlah rekaman yang dipindahkan dengan pemilihan langsung lebih sedikit dibandingkan dengan penyisipan langsung, penyortiran pemilihan langsung lebih baik.
* (2) Jika keadaan awal file pada dasarnya berurutan (mengacu pada urutan positif), penyisipan langsung, gelembung, atau penyortiran cepat acak harus digunakan;
* (3) Jika n besar, metode pengurutan dengan kompleksitas waktu O(nlgn) harus digunakan: pengurutan cepat, pengurutan heap, atau pengurutan gabungan.
*
*/
kelas publik Sortir {
/**
* Metode untuk menginisialisasi array pengujian
*
* @mengembalikan array yang diinisialisasi
*/
publik int[] buatArray() {
Acak acak = baru Acak();
int[] larik = int baru[10];
untuk (int saya = 0; saya < 10; saya++) {
array[i] = random.nextInt(100) - random.nextInt(100); // Hasilkan dua angka acak dan kurangi untuk memastikan bahwa ada angka negatif dalam angka yang dihasilkan.
}
System.out.println("==========urutan asli===========");
printArray(array);
kembalikan susunan;
}
/**
* Cetak elemen dalam array ke konsol
*
* @param sumber
*/
public void printArray(int[] data) {
untuk (int i : data) {
Sistem.keluar.cetak(i + " ");
}
Sistem.keluar.println();
}
/**
* Tukarkan posisi dua elemen tertentu dalam array
*
* @paramdata
* @paramx
* @param y
*/
pertukaran kekosongan pribadi(int[] data, int x, int y) {
int suhu = data[x];
data[x] = data[y];
data[y] = suhu;
}
/**
* Penyortiran gelembung ---- sejenis pengurutan pertukaran
* Metode: Bandingkan dua elemen yang berdekatan dan tukarkan jika perlu. Setelah setiap siklus selesai, elemen terbesar diberi peringkat terakhir (seperti mengurutkan dari kecil ke besar).
* Kinerja: jumlah perbandingan O(n^2),n^2/2; jumlah pertukaran O(n^2),n^2/4
*
* @paramdata
* Array yang akan diurutkan
* @param sortType
* Jenis penyortiran
* @kembali
*/
public void bubbleSort(int[] data, String sortType) {
if (sortType.equals("asc")) { // Pengurutan positif, dari kecil ke besar
// Jumlah putaran perbandingan
for (int i = 1; i < data.panjang; i++) {
// Bandingkan dua angka yang berdekatan, dan angka yang lebih besar akan muncul.
for (int j = 0; j < data.panjang - i; j++) {
jika (data[j] > data[j + 1]) {
// Tukar dua angka yang berdekatan
menukar(data, j, j+1);
}
}
}
} else if (sortType.equals("desc")) { // Urutkan dalam urutan terbalik, dari besar ke kecil
// Jumlah putaran perbandingan
for (int i = 1; i < data.panjang; i++) {
// Bandingkan dua angka yang berdekatan, dan angka yang lebih besar akan muncul.
for (int j = 0; j < data.panjang - i; j++) {
jika (data[j] < data[j + 1]) {
// Tukar dua angka yang berdekatan
menukar(data, j, j+1);
}
}
}
} kalau tidak {
System.out.println("Jenis pengurutan yang Anda masukkan salah!");
}
printArray(data);//Keluarkan nilai array setelah pengurutan gelembung
}
/**
* Metode penyortiran pilihan langsung----jenis penyortiran pilihan
* Metode: Dalam setiap pass, elemen terkecil (atau terbesar) dipilih dari elemen data yang akan diurutkan, dan urutannya ditempatkan di akhir array yang diurutkan hingga semua elemen data yang akan diurutkan tersusun.
* Performa: Jumlah perbandingan O(n^2),n^2/2
* Jumlah pertukaran O(n),n
* Jumlah pertukaran jauh lebih sedikit dibandingkan dengan bubble sort. Karena pertukaran membutuhkan lebih banyak waktu CPU dibandingkan perbandingan, pengurutan seleksi lebih cepat daripada pengurutan gelembung.
* Namun ketika N relatif besar, waktu CPU yang dibutuhkan untuk perbandingan mendominasi, sehingga performa saat ini tidak jauh berbeda dengan bubble sort, namun niscaya lebih cepat.
*
* @paramdata
* Array yang akan diurutkan
* @param sortType
* Jenis penyortiran
* @kembali
*
*/
public void selectSort(int[] data, String sortType) {
if (sortType.equals("asc")) { // Pengurutan positif, dari kecil ke besar
int indeks;
for (int i = 1; i < data.panjang; i++) {
indeks = 0;
for (int j = 1; j <= data.panjang - i; j++) {
jika (data[j] > data[indeks]) {
indeks = j;
}
}
//Tukarkan kedua angka pada posisi data.length-i dan indeks (nilai maksimum)
swap(data, data.panjang - i, indeks);
}
} else if (sortType.equals("desc")) { // Urutkan dalam urutan terbalik, dari besar ke kecil
int indeks;
for (int i = 1; i < data.panjang; i++) {
indeks = 0;
for (int j = 1; j <= data.panjang - i; j++) {
jika (data[j] < data[indeks]) {
indeks = j;
}
}
//Tukarkan kedua angka pada posisi data.length-i dan indeks (nilai maksimum)
swap(data, data.panjang - i, indeks);
}
} kalau tidak {
System.out.println("Jenis pengurutan yang Anda masukkan salah!");
}
printArray(data);//Keluarkan nilai array setelah penyortiran pilihan langsung
}
/**
*
* Sortir penyisipan
*
* Metode: Memasukkan record ke dalam daftar terurut yang telah diurutkan (mungkin daftar kosong), sehingga memperoleh daftar terurut baru dengan jumlah record bertambah 1.
* Performa: jumlah perbandingan O(n^2),n^2/4
* Jumlah salinan O(n),n^2/4
* Jumlah perbandingan rata-rata antara dua yang pertama, dan penyalinan memerlukan waktu CPU lebih sedikit dibandingkan pertukaran, sehingga kinerjanya lebih dari dua kali lipat dibandingkan pengurutan gelembung dan lebih cepat daripada pengurutan pilihan.
*
* @paramdata
* Array yang akan diurutkan
* @param sortType
* Jenis penyortiran
*/
public void insertSort(int[] data, String sortType) {
if (sortType.equals("asc")) { // Pengurutan positif, dari kecil ke besar
// Jumlah putaran perbandingan
for (int i = 1; i < data.panjang; i++) {
// Pastikan angka i+1 pertama sudah diurutkan
untuk (int j = 0; j < i; j++) {
jika (data[j] > data[i]) {
// Tukar dua angka pada posisi j dan i
menukar(data, saya, j);
}
}
}
} else if (sortType.equals("desc")) { // Urutkan dalam urutan terbalik, dari besar ke kecil
// Jumlah putaran perbandingan
for (int i = 1; i < data.panjang; i++) {
// Pastikan angka i+1 pertama sudah diurutkan
untuk (int j = 0; j < i; j++) {
jika (data[j] < data[i]) {
// Tukar dua angka pada posisi j dan i
menukar(data, saya, j);
}
}
}
} kalau tidak {
System.out.println("Jenis pengurutan yang Anda masukkan salah!");
}
printArray(data);//Keluarkan nilai array setelah penyortiran penyisipan
}
/**
*
* Metode untuk membalikkan array
*
* @paramdata
* susunan sumber
*/
kekosongan publik terbalik(int[] data) {
int panjang = data.panjang;
int temp = 0;//variabel sementara
untuk (int i = 0; i < panjang / 2; i++) {
suhu = data[i];
data[i] = data[panjang - 1 - i];
data[panjang - 1 - i] = suhu;
}
printArray(data);//Keluarkan nilai ke array yang dikonversi
}
/**
*
* Penyortiran cepat
*
* Penyortiran cepat menggunakan strategi bagi dan taklukkan untuk membagi suatu urutan (daftar) menjadi dua sub-urutan (sub-daftar).
*
*Langkah-langkahnya adalah:
* 1. Pilih elemen dari urutan, yang disebut "pivot",
* 2. Susun kembali barisan tersebut sehingga semua elemen yang lebih kecil dari nilai dasar ditempatkan di depan alas, dan semua elemen yang lebih besar dari nilai dasar ditempatkan di belakang alas (bilangan yang sama dapat ditempatkan di kedua sisi). Setelah pemisahan ini, datum berada pada posisi akhirnya. Ini disebut operasi partisi.
* 3. Mengurutkan subarray elemen yang lebih kecil dari nilai dasar dan subarray elemen yang lebih besar dari nilai dasar secara rekursif.
*
* Kasus terbawah dari rekursi adalah ketika ukuran array adalah nol atau satu, artinya selalu diurutkan. Walaupun terus berulang, algoritma ini akan selalu berakhir, karena pada setiap iterasi (iterasi) akan memindahkan minimal satu elemen ke posisi akhirnya.
*
* @paramdata
* Array yang akan diurutkan
* @param rendah
* @param tinggi
* @lihat SortTest#qsort(int[], int, int)
* @lihat SortTest#qsort_desc(int[], int, int)
*
*/
public void quickSort(int[] data, String sortType) {
if (sortType.equals("asc")) { // Pengurutan positif, dari kecil ke besar
qsort_asc(data, 0, data.panjang - 1);
} else if (sortType.equals("desc")) { // Urutkan dalam urutan terbalik, dari besar ke kecil
qsort_desc(data, 0, data.panjang - 1);
} kalau tidak {
System.out.println("Jenis pengurutan yang Anda masukkan salah!");
}
}
/**
*
* Implementasi khusus penyortiran cepat, penyortiran dalam urutan yang benar
*
* @paramdata
* @param rendah
* @param tinggi
*/
private void qsort_asc(int data[], int rendah, int tinggi) {
ke dalam i, j, x;
if (low < high) {//Kondisi ini digunakan untuk mengakhiri rekursi
saya = rendah;
j = tinggi;
x = data[i];
sementara (saya <j) {
sementara (i < j && data[j] > x) {
j--; //Cari bilangan pertama yang kurang dari x dari kanan ke kiri
}
jika (saya <j) {
data[i] = data[j];
saya++;
}
sementara (saya < j && data[i] < x) {
i++; //Cari bilangan pertama yang lebih besar dari x dari kiri ke kanan
}
jika (saya <j) {
data[j] = data[i];
J--;
}
}
data[i] = x;
qsort_asc(data, rendah, i - 1);
qsort_asc(data, i+1, tinggi);
}
}
/**
*
* Implementasi khusus penyortiran cepat, urutkan dalam urutan terbalik
*
* @paramdata
* @param rendah
* @param tinggi
*
*/
private void qsort_desc(int data[], int rendah, int tinggi) {
ke dalam i, j, x;
if (low < high) {//Kondisi ini digunakan untuk mengakhiri rekursi
saya = rendah;
j = tinggi;
x = data[i];
sementara (saya <j) {
sementara (i < j && data[j] < x) {
j--; //Cari bilangan pertama yang kurang dari x dari kanan ke kiri
}
jika (saya <j) {
data[i] = data[j];
saya++;
}
sementara (saya < j && data[i] > x) {
i++; //Cari bilangan pertama yang lebih besar dari x dari kiri ke kanan
}
jika (saya <j) {
data[j] = data[i];
J--;
}
}
data[i] = x;
qsort_desc(data, rendah, i - 1);
qsort_desc(data, i+1, tinggi);
}
}
/**
*
* Pencarian biner untuk posisi bilangan bulat tertentu dalam array bilangan bulat (rekursif)
*
* Pencarian daftar linier harus berupa daftar yang diurutkan
*
* @paramdataset
* @paramdata
* @parambeginIndex
* @paramendIndex
* @returnindex
*
*/
publik int binerSearch(int[] kumpulan data, int data, int startIndex,int endIndex) {
int midIndex = (beginIndex + endIndex) >>> 1; // Setara dengan mid = (rendah + tinggi)
// / 2, namun efisiensinya akan lebih tinggi
if (data < kumpulan data[beginIndex] || data > kumpulan data[endIndex] || beginIndex > endIndex)
kembali -1;
if (data < kumpulan data[indeks tengah]) {
kembalikan binerSearch(kumpulan data, data, indeks mulai, indeks tengah - 1);
} else if (data > kumpulan data[indeks tengah]) {
kembalikan binerSearch(kumpulan data, data, indeks tengah + 1, indeks akhir);
} kalau tidak {
kembali pertengahan Indeks;
}
}
/**
*
* Pencarian biner untuk posisi bilangan bulat tertentu dalam array bilangan bulat (non-rekursif)
*
* Pencarian daftar linier harus berupa daftar yang diurutkan
*
* @paramdataset
* @paramdata
* @returnindex
*
*/
publik int binerSearch(int[] kumpulan data, int data) {
int mulaiIndeks = 0;
int endIndex = kumpulan data.panjang - 1;
int indeks tengah = -1;
if (data < kumpulan data[beginIndex] || data > kumpulan data[endIndex] || beginIndex > endIndex)
kembali -1;
sementara (beginIndex <= endIndex) {
midIndex = (beginIndex + endIndex) >>> 1; // Setara dengan midIndex =
// (mulaiIndeks +
// endIndex) / 2, tetapi efisiensinya akan lebih tinggi
if (data < kumpulan data[indeks tengah]) {
indeks akhir = indeks tengah - 1;
} else if (data > kumpulan data[indeks tengah]) {
startIndex = indeks tengah + 1;
} kalau tidak {
kembali pertengahan Indeks;
}
}
kembali -1;
}
public static void main(String[] args) {
Sortir sortTest = Sortir baru();
int[] array = sortTest.createArray();
System.out.println("==========Setelah bubble sort (urutan positif)===========");
sortTest.bubbleSort(array, "asc");
System.out.println("==========Setelah bubble sort (urutan terbalik)===========");
sortTest.bubbleSort(array, "desc");
array = sortTest.createArray();
System.out.println("==========Setelah membalik array===========");
sortTest.reverse(array);
array = sortTest.createArray();
System.out.println("==========Setelah pengurutan seleksi (urutan positif)===========");
sortTest.selectSort(array, "asc");
System.out.println("==========Setelah pengurutan pilihan (urutan terbalik)===========");
sortTest.selectSort(array, "desc");
array = sortTest.createArray();
System.out.println("==========Setelah pengurutan penyisipan (urutan positif)===========");
sortTest.insertSort(array, "asc");
System.out.println("==========Setelah pengurutan penyisipan (urutan terbalik)===========");
sortTest.insertSort(array, "desc");
array = sortTest.createArray();
System.out.println("==========Setelah pengurutan cepat (urutan positif)===========");
sortTest.quickSort(array, "asc");
sortTest.printArray(array);
System.out.println("==========Setelah pengurutan cepat (urutan terbalik)===========");
sortTest.quickSort(array, "desc");
sortTest.printArray(array);
System.out.println("==========Pencarian biner dalam array===========");
System.out.println("Nomor yang anda cari ada di" + sortTest.binarySearch(array, 74)
+ "kursi. (Subskrip dihitung dari 0)");
}
}