【2019春招準備:8.並べ替え】
【内容】【補足】時間複雑度 ソート方法
時間の複雑さ
あんていせい
きゅうそくれつ
N log(N)
スタック
N log(N)
ふあんてい速排の2つの理解構想:単回交換法と二回交換法 スタック並べ替え完全二叉木:スタック(従って配列で表すことができる下標は1からそうでないと魔性である)大頂スタック小頂スタック 1−n n/2は最後の非リーフノードの下付き
時間の複雑さ
あんていせい
きゅうそくれつ
N log(N)
スタック
N log(N)
ふあんてい
package q3_sort;
import java.util.Scanner;
/**
* （NlogN）
* @author ziboris
* @date 2018 11 26 9:37:04
*
*/
public class Test1_QuickSort {
public static void quick_sort(int[] a, int left, int right) {
if (left < right) {
// i,j x
int i = left, j = right, x = a[left];
while (i < j) {// while while
while (i < j && a[j] >= x)
j--; // i j ， while ;x i
//
if (i < j)
a[i++] = a[j];
while (i < j && a[i] < x)
++i;
if (i < j)
a[j--] = a[i];
}
// i==j
a[i] = x;
quick_sort(a, left, i - 1);
quick_sort(a, i + 1, right);
}
}
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
int[] a = new int[n];//
// System.out.println(a.length);
for (int i = 0; i < n; ++i) {
a[i] = scanner.nextInt();
}
quick_sort(a, 0, a.length - 1);
for (int i : a) {
System.out.println(i);
}
}
}
package q3_sort;
import java.util.Arrays;
import java.util.Scanner;
public class Test2_HeapSort {
static int n = 10;
static int[] a = new int[11];// ;
public static void downAdjust(int low, int high) {
int i = low;
int j = i * 2;
while (j <= high) {
//
if (j + 1 <= high && a[j + 1] > a[j])
j = j + 1;// ij j
// ，
if (a[i] < a[j]) {
int temp = a[j];
a[j] = a[i];
a[i] = temp;
i = j;
j = j * 2;
} else {
break;
}
}
}
public static void heap_sort() {
// create_heap();
for (int i = n / 2; i >= 1; --i) {
downAdjust(i, n);
}
// sort
for (int i = n; i > 1; --i) {
int temp = a[1];
a[1] = a[i];
a[i] = temp;
downAdjust(1, i - 1);
}
}
public static void main(String[] args) {
// 72 6 57 88 60 42 83 73 48 85
Scanner scanner = new Scanner(System.in);
n = scanner.nextInt();
// System.out.println(a.length);
// 1
for (int i = 1; i <= n; ++i) {
a[i] = scanner.nextInt();
}
heap_sort();
System.out.println(Arrays.toString(a));
}
}