时间复杂度 O(1) < O(lgn) < O(n)
2.1 插入排序 O(n^2)
python:
list = [5, 2, 4, 6, 1, 3]
for i in range(1, len(list)):
x = list[i]
j = i - 1
while j >= 0 and list[j] > x:
list[j + 1] = list[j]
list[j] = x
j -= 1
print list
java:
private static void insertSort(int[] ints) {
int i, j;
for (i = 1; i < ints.length; i++) {
int x = ints[i];
j = i - 1;
while (j >= 0 && x < ints[j]) {
ints[j + 1] = ints[j];
ints[j] = x;
j --;
}
}
}
2.2 分治策略 O(nlgn)
import sys
list = [2, 4, 5, 7, 1, 2, 3, 6]
m = len(list) / 2
l1 = list[0:m]
l2 = list[m:]
l1.append(sys.maxint)
l2.append(sys.maxint)
i = 0
j = 0
for k in range(0, len(list)):
if l1[i] <= l2[j]:
list[k] = l1[i]
i +=1
else:
list[k] = l2[j]
j +=1
print list
java:
public class Main2 {
public static void main(String[] args) {
int[] ints = new int[]{2, 4, 7, 1, 4, 34, 64, 14, 85, 123, 52};
mergeSort(ints, 0,ints.length - 1);
System.out.println(Arrays.toString(ints));
}
private static void mergeSort(int[] ints, int l, int r) {
if (l >= r) {
return;
}
int mid = (l + r) / 2;
mergeSort(ints, l, mid);
mergeSort(ints, mid + 1, r);
System.out.println("before:" + mid);
merge(ints, l, mid, r);
System.out.println("after:" + mid);
}
private static void merge(int[] ints, int l, int m, int r) {
int[] tmp = new int[ints.length];
int rs = m + 1; // right part start index
int i = l;
int ci = l; // for copy array index
while (l <= m && rs <= r) {
if (ints[l] <= ints[rs]) {
tmp[i++] = ints[l++];
} else {
tmp[i++] = ints[rs++];
}
}
while (l <= m) {
tmp[i++] = ints[l++];
}
while (rs <= r) {
tmp[i++] = ints[rs++];
}
while (ci <=r) {
ints[ci] = tmp[ci];
ci++;
}
}
private static void insertSort(int[] ints) {
int i, j;
for (i = 1; i < ints.length; i++) {
int x = ints[i];
j = i - 1;
while (j >= 0 && x < ints[j]) {
ints[j + 1] = ints[j];
ints[j] = x;
j--;
}
}
}
}
2.3 分治策略(不用哨兵)
import sys
list = [2, 4, 5, 7, 1, 2, 3, 6, 8, 8]
m = len(list) / 2
l1 = list[0:m]
l2 = list[m:]
i = 0
j = 0
for k in range(0, len(list)):
if i >= len(l1) and j < len(l2):
list[k] = l2[j]
j += i
continue
elif j >= len(l2) and i < len(l1):
list[k] = l1[i]
i += 1
continue
if l1[i] <= l2[j]:
list[k] = l1[i]
i +=1
else:
list[k] = l2[j]
j +=1
print list
2.4 冒泡排序
list = [2, 4, 5, 7, 1, 2, 3, 6, 8, 8]
for i in xrange(0, len(list)):
for j in xrange(len(list) - 1, i, -1):
x = list[j]
y = list[j - 1]
if x < y:
list[j] = y
list[j - 1] = x
print list
2.5 max subarray(??) 分治策略
import sys
list = [13, -3, -25, 20, -3, -16, -23, 18, 20, -7, 12, -5, -22, -4, 7]
m = len(list) / 2
left_sum = -sys.maxint - 1
sum = 0
for i in xrange(m, 0, -1):
sum += list[i]
if sum > left_sum:
left_sum = sum
max_left = i
right_sum = -sys.maxint - 1
sum = 0
for j in range(m + 1, len(list)):
sum += list[j]
if sum > right_sum:
right_sum = sum
max_right = j
print max_left, max_right, left_sum + right_sum
近期评论