Last Order
0%

常见排序算法的实现

发表于 更新于 分类于

排序算法

之前写过的脚本语言全都忘了，这里打算利用排序算法复习一下。。。。

冒泡排序

冒泡排序(En)

冒泡排序(CH)

优化点：

  1. 每趟排序会使一个数字到达到达它的最终位置，所以每趟冒泡的次数最大是length-1-i；
  2. 在一趟冒泡中如果没有发生位置交换，则认为已经是有序队列，不再进行冒泡；

Java版本：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
public class Main {
    public static void main(String[] args) {
        int[] numbers = getIntArray();
        // bubberSort(numbers);
        bubberSort2(numbers);
    }
    
    private static int[] getIntArray() {
        Random random = new Random();
        int length = 20;
        int[] numbers = new int[length];
        for (int i = 0; i < length; i++) {
            numbers[i] = random.nextInt(100);
        }
        return numbers;
    }
    
    public static void bubberSort(numbers)(int[] numbers) {
        int length = numbers.length;
        for (int i = 0; i < length - 1; i++) {
            for (int j = 0; j < length - 1 - i; j++) {
                if (numbers[j] > numbers[j + 1]) {
                    swap(numbers, j, j+1);
                }
            }
        }
        printArray(numbers);
    }

    public static void bubberSort2(int[] numbers) {
        int length = numbers.length;
        boolean changed = false;
        for (int i = 0; i < length - 1; i++) {
            for (int j = 0; j < length - 1 - i; j++) {
                if (numbers[j] > numbers[j + 1]) {
                    swap(numbers, j, j + 1);
                    changed = true;
                }
            }
            if (!changed) {
                break;
            }
            changed = false ;
        }
        printArray(numbers);
    }

    private static void printArray(int[] arr) {
        IntStream.of(arr).forEach(x -> System.out.print("," + x));
        System.out.println();
    }

    private static void swap(int[] data, int i, int j) {
        if (i == j) {
            return;
        }
        data[i] = data[i] + data[j];
        data[j] = data[i] - data[j];
        data[i] = data[i] - data[j];
    }
}

javaScript:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
let numbers = [82,37,10,69,1,92,6,13,77,33,47,12,23,82,71,57,58,51,57,75];

function bubber_sort(arr){
	if (arr instanceof Array){
		for(let i = 0 ;i< arr.length-1;i++){
			for(let j=0;j<arr.length-i-1;j++){
				if(arr[j]>arr[j+1]){
					(function(arr,x,y){
						arr[x] = arr[x] ^ arr[y] ;
						arr[y] = arr[x] ^ arr[y] ;
						arr[x] = arr[x] ^ arr[y] ;
					})(arr,j,j+1);
				}
			}
		}
		console.log(arr.join());
	}
}
bubber_sort(numbers);

c++:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
#include <iostream>

#define GET_LEN(array, len)                     \
    {                                           \
        len = sizeof(array) / sizeof(array[0]); \
    }

void swap(int arr[], int x, int y)
{
    arr[x] = arr[x] ^ arr[y];
    arr[y] = arr[x] ^ arr[y];
    arr[x] = arr[x] ^ arr[y];
}

void swap(int *a ,int *b){
    *a = *a^*b ;
    *b = *a^*b ;
    *a = *a^*b ;
}

void swap(int &a ,int &b){
    a = a^b ;
    b = a^b ;
    a = a^b ;
}

void bubber_sort(int numbers[],int length){
    for (int i = 0; i < length - 1; i++)
    {
        for (int j = 0; j < length - 1 - i; j++)
        {
            if (numbers[j] > numbers[j + 1])
            {
                // swap(numbers, j, j + 1);
                // swap(&numbers[j],&numbers[j+1]);
                // swap(numbers[j],numbers[j+1]);
                std::swap(numbers[j],numbers[j+1]);
            }
        }
    }

    for (int i = 0; i < length; i++)
    {
        std::cout << numbers[i] << ",";
    }
}

int main()
{
    int numbers[] = {82,37,10,69,1,92,6,13,77,33,47,12,23,82,71,57,58,51,57,75};
    int length;
    GET_LEN(numbers, length);
    bubber_sort(numbers,length);
    return 0;
}

python:

1
2
3
4
5
6
7
8
9
10
numbers = [82,37,10,69,1,92,6,13,77,33,47,12,23,82,71,57,58,51,57,75];

def bubber_sort(numbers):
	for i in range(len(numbers)-1):
		for j in range(len(numbers)-1-i):
			if numbers[j] > numbers[j+1]:
				numbers[j],numbers[j+1] = numbers[j+1],numbers[j]
	print(numbers)

bubber_sort(numbers)

TypeScript(啊，好像和js一样，改一下解构赋值凑个数…):

1
2
3
4
5
6
7
8
9
10
11
12
13
let numbers = [82,37,10,69,1,92,6,13,77,33,47,12,23,82,71,57,58,51,57,75];

function bubber_sort(arr:number[]){
	for(let i = 0 ;i< arr.length-1;i++){
        for(let j=0;j<arr.length-i-1;j++){
        	if(arr[j]>arr[j+1]){
                [arr[j],arr[j+1]]=[arr[j+1],arr[j]]
       		}
       	}
    }
	console.log(arr.join());	
}
bubber_sort(numbers);

选择排序

选择排序(En)

选择排序(CH)

每一趟选出一个最小(最大)的放到最终位置。

Java：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
public class Main {
    public static void main(String[] args) {
        int[] numbers = getIntArray();
        selectionSort(numbers);
    }
    
    private static int[] getIntArray() {
        Random random = new Random();
        int length = 20;
        int[] numbers = new int[length];
        for (int i = 0; i < length; i++) {
            numbers[i] = random.nextInt(100);
        }
        return numbers;
    }
    
    public static void printArray(int[] arr) {
        IntStream.of(arr).forEach(x -> System.out.print("," + x));
        System.out.println();
    }

    private static void swap(int[] data, int i, int j) {
        if (i == j) {
            return;
        }
        data[i] = data[i] + data[j];
        data[j] = data[i] - data[j];
        data[i] = data[i] - data[j];
    }
    
    public static void selectionSort(int[] arr) {
        int min;
        for (int i = 0; i < arr.length; i++) {
            min = i;
            for (int j = i; j < arr.length; j++) {
                if (arr[j] < arr[min]) {
                    min = j;
                }
            }
            if(min!=i){
                swap(arr,min,i);
            }
        }
        printArray(arr);
    }
}

JavaScript:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
let numbers = [82,37,10,69,1,92,6,13,77,33,47,12,23,82,71,57,58,51,57,75];

function selection_sort(arr){
    let min = 0 ;
    for(let i = 0 ;i< arr.length;i++){
        min = i ;
        for(let j=i;j<arr.length;j++){
            if(arr[j]<arr[min]){
                min = j ;
            }
        }
        if(min != i){
            [arr[i],arr[min]]=[arr[min],arr[i]]
        }
    }
    console.log(arr.join());
}
selection_sort(numbers)

Python:

1
2
3
4
5
6
7
8
9
10
11
12
13
numbers = [82,37,10,69,1,92,6,13,77,33,47,12,23,82,71,57,58,51,57,75];

def selection_sort(numbers):
	for i in range(len(numbers)):
		min=i
		for j in range(i,len(numbers)):
			if numbers[min] > numbers[j]:
				min=j
		if min != i :
			numbers[i],numbers[min] = numbers[min],numbers[i]
	print(numbers)

selection_sort(numbers)

C++:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#include <iostream>

#define GET_LEN(array, len)                     \
    {                                           \
        len = sizeof(array) / sizeof(array[0]); \
    }

void swap(int &a ,int &b){
    a = a^b ;
    b = a^b ;
    a = a^b ;
}

void selection_sort(int numbers[],int length){
    int min = 0 ;
    for (int i = 0; i < length ; i++)
    {
        min=i;
        for (int j = i; j < length ; j++)
        {
            if (numbers[min] > numbers[j])
            {
                 min = j ;
            }
        }
        if(min != i){
            swap(numbers[min],numbers[i]);
        }
    }

    for (int i = 0; i < length; i++)
    {
        std::cout << numbers[i] << ",";
    }
}

int main()
{
    int numbers[] = {82,37,10,69,1,92,6,13,77,33,47,12,23,82,71,57,58,51,57,75};
    int length;
    GET_LEN(numbers, length);
    selection_sort(numbers,length);
    return 0;
}

插入排序

插入排序(En)

插入排序(CH)

Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
public class Main {
    public static void main(String[] args) {
        int[] numbers = getIntArray();
        insertionSort(numbers);
    }
    
    private static int[] getIntArray() {
        Random random = new Random();
        int length = 20;
        int[] numbers = new int[length];
        for (int i = 0; i < length; i++) {
            numbers[i] = random.nextInt(100);
        }
        return numbers;
    }
    
    public static void printArray(int[] arr) {
        IntStream.of(arr).forEach(x -> System.out.print("," + x));
        System.out.println();
    }

    private static void swap(int[] data, int i, int j) {
        if (i == j) {
            return;
        }
        data[i] = data[i] + data[j];
        data[j] = data[i] - data[j];
        data[i] = data[i] - data[j];
    }
    
    public static void insertionSort(int[] arr) {
        for (int i = 1; i < arr.length; i++) {
            int insertIndex = i ;
            int temp = arr[i];
            for (int j = i; j > 0; j--) {
                if (temp < arr[j - 1]) {
                    arr[j] = arr[j - 1];
                    insertIndex = j - 1;
                }
            }
            arr[insertIndex] = temp;
        }
        printArray(arr);
    }
}

JavaScript:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
let numbers = [82,37,10,69,1,92,6,13,77,33,47,12,23,82,71,57,58,51,57,75];

function insertion_sort(arr){
    for(let i = 0 ;i< arr.length;i++){
        let index = j ;
        let key = arr[i] ;
        for(let j=i;j>0;j--){
            if(key<arr[j-1]){
                arr[j] = arr[j-1] ;
                index = j-1;
            }
        }
        arr[index] = key ;
    }
    console.log(arr.join());
}

insertion_sort(numbers)

python:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
numbers = [82,37,10,69,1,92,6,13,77,33,47,12,23,82,71,57,58,51,57,75];

def insertion_sort(numbers):
	for i in range(len(numbers)):
		key = numbers[i]
		index = i
		for j in range(i,0,-1):
			if key < numbers[j-1]:
				numbers[j] = numbers[j-1]
				index = j-1
		numbers[index] = key
	print(numbers)

insertion_sort(numbers)

C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include <iostream>

#define GET_LEN(array, len)                     \
    {                                           \
        len = sizeof(array) / sizeof(array[0]); \
    }

void insertion_sort(int numbers[],int length){
    for (int i = 0; i < length ; i++)
    {
        int index=i;
        int key = numbers[i];
        for (int j = i; j > 0 ; j--)
        {
            if (key < numbers[j-1])
            {
                numbers[j] = numbers[j-1] ;
                index= j-1 ;
            }
        }
        numbers[index]= key ;
    }

    for (int i = 0; i < length; i++)
    {
        std::cout << numbers[i] << ",";
    }
}

int main()
{
    int numbers[] = {82,37,10,69,1,92,6,13,77,33,47,12,23,82,71,57,58,51,57,75};
    int length;
    GET_LEN(numbers, length);
    insertion_sort(numbers,length);
    return 0;
}

快速排序

快速排序(En)

快速排序(CH)

快速排序需要注意的是，不要太过于看重左右节点交换的过程，每一趟排序只是为了分成左右两个子段。比如可以不用左右交换，直接从头到尾遍历，遇到比key小的值就放到key的左边，这样子也可以得到结果

Java:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
public class Main {
    public static void main(String[] args) {
        int[] numbers = getIntArray();
        quickSort(numbers);
    }
    
    private static int[] getIntArray() {
        Random random = new Random();
        int length = 20;
        int[] numbers = new int[length];
        for (int i = 0; i < length; i++) {
            numbers[i] = random.nextInt(100);
        }
        return numbers;
    }
    
    public static void printArray(int[] arr) {
        IntStream.of(arr).forEach(x -> System.out.print("," + x));
        System.out.println();
    }
	
    public static void quickSort(int[] arr) {
        quicksortInternal(arr, 0, arr.length - 1);
        printArray(arr);
    }

    private static void quicksortInternal(int[] arr, int start, int end) {
        if (start >= end) {
            return;
        }
        int index = quicksortPartion(arr, start, end);
        quicksortInternal(arr, start, index - 1);
        quicksortInternal(arr, index + 1, end);
    }

    private static int quicksortPartion(int[] arr, int start, int end) {
        int pivot = arr[start];
        while (start < end) {
            while (arr[end] >= pivot && start != end) {
                end--;
            }
            arr[start] = arr[end];
            while (arr[start] <= pivot && start != end) {
                start++;
            }
            arr[end] = arr[start];
        }
        arr[start] = pivot;
        return start;
    }
    
    // 这里也可以模仿下面的js方法写
    public static void quickSort2(int[] numbers){
        List<Integer> arr = Arrays.stream(numbers).boxed().collect(Collectors.toList());
        List<Integer> list = new ArrayList<>(arr.size());
        quickSortInternal2(arr,list);
        System.out.println(list.toString());
    }

    public static void quickSortInternal2(List<Integer> arr,List<Integer> result){
        if(arr.size() == 0){
            return;
        }
        if(arr.size() == 1){
            result.add(arr.get(0));
            return;
        }
        quickSortInternal2(arr.stream().filter(x -> x < arr.get(0)).collect(Collectors.toList()),result);
        result.addAll(arr.stream().filter(x -> x.equals(arr.get(0))).collect(Collectors.toList()));
        quickSortInternal2(arr.stream().filter(x -> x > arr.get(0)).collect(Collectors.toList()),result);
    }
}

JavaScript:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
let numbers = [82,37,10,69,1,92,6,13,77,33,47,12,23,82,71,57,58,51,57,75];

function quick_sort(arr){
    quick_sort_internal(arr,0,arr.length-1);
    console.log(arr.join());
}

function quick_sort_internal(arr,lo,hi){
    if(lo >= hi){
       return ;
    }
    let index = (function(arr,lo,hi){
        let pivot = arr[lo];
        while(lo < hi){
            while(arr[hi] >= pivot && lo < hi ){
                hi--;
            }
            arr[lo] = arr[hi]
            while(arr[lo] <= pivot && lo < hi){
                lo++;
            }
            arr[hi] = arr[lo];
        }
        arr[lo] = pivot;
        return lo;
    })(arr,lo,hi)
    quick_sort_internal(arr,lo,index-1);
    quick_sort_internal(arr,index+1,hi);
}

quick_sort(numbers)


//第二种方法。。。
const qsort = xs => xs.length===0?xs: [
    ...qsort(xs.filter(x=>x<xs[0])),
    ...xs.filter(x=>x===xs[0]),
    ...qsort(xs.filter(x=>x>xs[0]))
]
qsort([...numbers])

Python:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
numbers = [82,37,10,69,1,92,6,13,77,33,47,12,23,82,71,57,58,51,57,75];

def quick_sort(numbers):
	quick_sort_internal(numbers,0,len(numbers)-1)
	print(numbers)
    
def quick_sort_internal(numbers,lo,hi):
    if lo >= hi :
        return 
    index = quick_sort_partition(numbers,lo,hi)
    print('index =' + str(index) )
    quick_sort_internal(numbers,lo,index-1)
    quick_sort_internal(numbers,index+1,hi)


def quick_sort_partition(numbers,lo,hi):
    pivot = numbers[lo]
    while lo<hi:
        while numbers[hi] >= pivot and lo < hi :
            hi=hi-1
        numbers[lo]=numbers[hi]
        while numbers[lo] <= pivot and lo < hi :
            lo=lo+1
        numbers[hi] = numbers[lo]
    numbers[lo] = pivot
    return lo

quick_sort(numbers[:])

## 这里也可以模仿上面的js方法写

C++:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#include <iostream>

#define GET_LEN(array, len)                     \
    {                                           \
        len = sizeof(array) / sizeof(array[0]); \
    }

int quick_sort_partition(int numbers[] ,int lo,int hi){
    int pivot = numbers[lo];
    while( lo < hi){
        while( numbers[hi] >= pivot && lo < hi){
            hi--;
        }
        numbers[lo] = numbers[hi];
        while( numbers[lo] <= pivot && lo < hi){
            lo++;
        }
        numbers[hi] = numbers[lo];
    }
    numbers[lo] = pivot ;
    return lo ;
}

void quick_sort_internal(int numbers[],int lo,int hi){
    if(lo >= hi){
        return;
    }
    int index = quick_sort_partition(numbers,lo,hi);
    quick_sort_internal(numbers,lo,index-1);
    quick_sort_internal(numbers,index+1,hi);
}

void quick_sort(int numbers[],int length){
    quick_sort_internal(numbers,0,length-1);
    for (int i = 0; i < length; i++)
    {
        std::cout << numbers[i] << ",";
    }
}

int main()
{
    int numbers[] = {82,37,10,69,1,92,6,13,77,33,47,12,23,82,71,57,58,51,57,75};
    int length;
    GET_LEN(numbers, length);
    quick_sort(numbers,length);
    return 0;
}

希尔排序

Java:

1

JavaScript:

1

Python

1

C++:

1

归并排序

归并排序(En)

归并排序(CH)

Java:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
public class Main {
    public static void main(String[] args) {
        int[] numbers = getIntArray();
        quickSort(numbers);
    }
    
    private static int[] getIntArray() {
        Random random = new Random();
        int length = 20;
        int[] numbers = new int[length];
        for (int i = 0; i < length; i++) {
            numbers[i] = random.nextInt(100);
        }
        return numbers;
    }
    
    public static void printArray(int[] arr) {
        IntStream.of(arr).forEach(x -> System.out.print("," + x));
        System.out.println();
    }
	
    public static void mergeSort(int[] numbers) {
        mergeSortInternal(numbers, 0, numbers.length - 1);
        printArray(numbers);
    }

    public static void mergeSortInternal(int[] numbers, int start, int end) {
        if (start >= end) {
            return;
        }
        int middle = (start + end) / 2;
        mergeSortInternal(numbers, start, middle);
        mergeSortInternal(numbers, middle+1, end);
//        mergeLeftAndRight(numbers, start, end);
        merge(numbers, start,middle, end);
    }
	
    //正经写法。。
    private static void merge(int[] numbers, int left, int middle, int right) {
        int lp = left;
        int rp = middle + 1;
        int tp = 0;
        int[] temp = new int[right - left + 1];

        while (lp <= middle && rp <= right) {
            if (numbers[lp] <= numbers[rp]) {
                temp[tp++] = numbers[lp++];
            } else {
                temp[tp++] = numbers[rp++];
            }
        }
        while (lp <= middle) {
            temp[tp++] = numbers[lp++];
        }
        while (rp <= right) {
            temp[tp++] = numbers[rp++];
        }
        for (int i = 0; i < temp.length; i++) {
            numbers[i + left] = temp[i];
        }
    }

    //使用插入排序来合并左右数组，效率会损失
    private static void mergeLeftAndRight(int[] numbers, int start, int end) {
        for (int i = start + 1; i < end + 1; i++) {
            int insertIndex = i;
            int temp = numbers[i];
            for (int j = i; j > start; j--) {
                if (temp < numbers[j - 1]) {
                    numbers[j] = numbers[j - 1];
                    insertIndex = j - 1;
                }
            }
            numbers[insertIndex] = temp;
        }
    }
}

JavaScript:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
let numbers = [82,37,10,69,1,92,6,13,77,33,47,12,23,82,71,57,58,51,57,75];

function merge_sort(numbers){
    merge_sort_internal(numbers,0,numbers.length-1);
    console.log(numbers.join());
}

function merge_sort_internal(numbers,left,right){
    if(left >= right){
        return;
    }
    let middle = Math.floor((left+right)/2);
    merge_sort_internal(numbers,left,middle);
    merge_sort_internal(numbers,middle+1,right);
    (function(numbers,l,m,r){
        let lp = l ;
        let rp = m+1 ;
        let temp = [];
        while (lp <= m && rp <= r) {
            if (numbers[lp] <= numbers[rp]) {
                temp.push(numbers[lp++]);
            } else {
                temp.push(numbers[rp++]);
            }
        }
        while (lp <= m) {
            temp.push(numbers[lp++]);
        }
        while (rp <= r) {
            temp.push(numbers[rp++]);
        }
        for (let i = 0; i < temp.length; i++) {
            numbers[i + l] = temp[i];
        } 
    })(numbers,left,middle,right);
}
merge_sort(numbers)

Python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
numbers = [82,37,10,69,1,92,6,13,77,33,47,12,23,82,71,57,58,51,57,75];

def merge_sort(numbers):
	merge_sort_internal(numbers,0,len(numbers)-1)
	print(numbers)

def merge_sort_internal(nums,left,right):
    if left>=right :
        return
    middle = int((left+right)/2)
    merge_sort_internal(nums,left,middle)
    merge_sort_internal(nums,middle+1,right)
    merge_left_and_right(nums,left,middle,right)

def merge_left_and_right(numbers,l,m,r):
    lp = l
    rp = m+1
    temp = []
    while lp <=m and rp <=r:
        if numbers[lp] <= numbers[rp] :
            temp.append(numbers[lp]);
            lp = lp+1
        else :
            temp.append(numbers[rp])
            rp = rp +1 
    while lp <= m :
        temp.append(numbers[lp])
        lp = lp+1
    while rp <= r :
        temp.append(numbers[rp])
        rp = rp+1
    for i in range(len(temp)) :
        numbers[i + l] = temp[i]

merge_sort(numbers[:])

C++:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
#include <iostream>

#define GET_LEN(array, len)                     \
    {                                           \
        len = sizeof(array) / sizeof(array[0]); \
    }

void merge_sort_merge(int numbers[] ,int left,int middle,int right){
    int lp = left;
    int rp = middle + 1;
    int tp = 0;
    int * temp  = new int[right - left + 1];

    while (lp <= middle && rp <= right) {
		temp[tp++] = numbers[lp] <= numbers[rp] ? numbers[lp++]:numbers[rp++];
    }
    while (lp <= middle) {
        temp[tp++] = numbers[lp++];
    }
    while (rp <= right) {
        temp[tp++] = numbers[rp++];
    }
    for (int i = 0; i < right - left + 1; i++) {
        numbers[i + left] = temp[i];
    }
    
    delete[] temp;
}

void merge_sort_internal(int numbers[],int left,int right){
    if(left >= right){
        return;
    }
    int middle = (left+right)/2;
    merge_sort_internal(numbers,left,middle);
    merge_sort_internal(numbers,middle+1,right);
    merge_sort_merge(numbers,left,middle,right);
}

void merge_sort(int numbers[],int length){
    merge_sort_internal(numbers,0,length-1);
    for (int i = 0; i < length; i++)
    {
        std::cout << numbers[i] << ",";
    }
}

int main()
{
    int numbers[] = {82,37,10,69,1,92,6,13,77,33,47,12,23,82,71,57,58,51,57,75};
    int length;
    GET_LEN(numbers, length);
    merge_sort(numbers,length);
    return 0;
}

堆排序

堆排序(En)

堆排序(CH)

堆分为大根堆和小根堆。

堆排序则是分为几个步骤：

  1. 建堆

    建堆有两种方式，一种是对数据从0开始执行插入操作，每次插入后调整。

    一种是直接从 len/2 处向0处开始调整，大多数排序都是以这种方式建堆。

  2. 交换根节点和最末节点，然后对len-1的数据重新建堆，用大根堆的时候根节点最大，此时此最大值会在最末节点位置处。

  3. 重复第二步，直到建堆的数据数量等于1。

Java:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
public class Main {
    public static void main(String[] args) {
        int[] numbers = getIntArray();
        heapSort(numbers);
    }
    
    private static int[] getIntArray() {
        Random random = new Random();
        int length = 20;
        int[] numbers = new int[length];
        for (int i = 0; i < length; i++) {
            numbers[i] = random.nextInt(100);
        }
        return numbers;
    }
    
    public static void printArray(int[] arr) {
        IntStream.of(arr).forEach(x -> System.out.print("," + x));
        System.out.println();
    }

    private static void swap(int[] data, int i, int j) {
        if (i == j) {
            return;
        }
        data[i] = data[i] + data[j];
        data[j] = data[i] - data[j];
        data[i] = data[i] - data[j];
    }
    
     public static void heapSort(int[] arr) {
        int end = arr.length - 1;
        do {
            buildMaxHeap(arr, end);
            swap(arr, 0, end);
            end--;
        } while (end > 0);
        printArray(arr);
    }

    private static void buildMaxHeap(int[] arr, int end) {
        for (int i = end / 2; i >= 0; i--) {
            HeapAdjust(arr, end, i);
        }
    }

    private static void HeapAdjust(int[] arr, int end, int adjustNode) {
        int left = 2 * adjustNode + 1;
        int right = 2 * adjustNode + 2;
        int maxPosition = adjustNode;
        if (left > end) {
            //没有子节点
        } else if (right > end) {
            //只有一个左子节点
            if (arr[left] > arr[adjustNode]) {
                swap(arr, left, adjustNode);
                maxPosition = left;
            }
        } else {
            int bigger = arr[left] < arr[right] ? right : left;
            if (arr[adjustNode] < arr[bigger]) {
                swap(arr, adjustNode, bigger);
                maxPosition = bigger;
            }
        }
        if (maxPosition != adjustNode) {  //说明这个节点没有调整，最终一定会到叶子节点或者无须调整而停止递归
            HeapAdjust(arr, end, maxPosition);
        }
    }
}

JavaScript:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
let numbers = [82,37,10,69,1,92,6,13,77,33,47,12,23,82,71,57,58,51,57,75];

function heap_sort(numbers){
    let end = numbers.length - 1;
    do {
        build_max_heap(numbers, end);
        [numbers[0],numbers[end]] =  [numbers[end],numbers[0]] ;
        end--;
    } while (end > 0);
    console.log(numbers.join());
}

function build_max_heap(arr,end) {
    for (let i = Math.floor(end / 2); i >= 0; i--) {
        heap_adjust(arr, end, i);
    }
}

function heap_adjust(arr, end, adjust_node) {
    let left = 2 * adjust_node + 1;
    let right = 2 * adjust_node + 2;
    let maxPosition = adjust_node;
    if (left > end) {
    } else if (right > end) {
        if (arr[left] > arr[adjust_node]) {
            [arr[left],arr[adjust_node]] =  [arr[adjust_node],arr[left]] ;
            maxPosition = left;
        }
    } else {
        let bigger = arr[left] < arr[right]?right:left;
        if (arr[adjust_node] < arr[bigger]) {
            [arr[bigger],arr[adjust_node]] =  [arr[adjust_node],arr[bigger]] ;
            maxPosition = bigger;
        }
    }
    if (maxPosition != adjust_node) {  
        heap_adjust(arr, end, maxPosition);
    }
}

heap_sort([...numbers])

Python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
numbers = [82,37,10,69,1,92,6,13,77,33,47,12,23,82,71,57,58,51,57,75]

def heap_sort(numbers):
    end = len(numbers) - 1
    while True :
        build_max_heap(numbers, end)
        numbers[0],numbers[end] =  numbers[end],numbers[0] 
        end = end -1 
        if end < 0 :
            break 
    print(numbers)

def build_max_heap(arr,end) :
    for i in range(int(end / 2),-1,-1):
        heap_adjust(arr, end, i)

def heap_adjust(arr, end, adjust_node) :
    left = 2 * adjust_node + 1
    right = 2 * adjust_node + 2
    maxPosition = adjust_node
    if left > end :
        pass
    elif right > end :
        if arr[left] > arr[adjust_node] :
            arr[left],arr[adjust_node] =  arr[adjust_node],arr[left] 
            maxPosition = left
    else :
        bigger = right if arr[left] < arr[right] else left;
        if arr[adjust_node] < arr[bigger] :
            arr[bigger],arr[adjust_node] = arr[adjust_node],arr[bigger]
            maxPosition = bigger
    if maxPosition != adjust_node :  
        heap_adjust(arr, end, maxPosition)

heap_sort(numbers[:])

C++:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
#include <iostream>

#define GET_LEN(array, len)                     \
    {                                           \
        len = sizeof(array) / sizeof(array[0]); \
    }

void swap(int &a ,int &b){
    a = a^b ;
    b = a^b ;
    a = a^b ;
}

void heap_adjust(int arr[] ,int end,int adjust_node){
    int left = 2 * adjust_node + 1;
    int right = 2 * adjust_node + 2;
    int maxPosition = adjust_node;
    if (left > end) {
        //没有子节点
    } else if (right > end) {
        //只有一个左子节点
        if (arr[left] > arr[adjust_node]) {
            swap(arr[left], arr[adjust_node]);
            maxPosition = left;
        }
    } else {
        int bigger = arr[left] < arr[right] ? right : left;
        if (arr[adjust_node] < arr[bigger]) {
            swap(arr[adjust_node], arr[bigger]);
            maxPosition = bigger;
        }
    }
    if (maxPosition != adjust_node) {  
        heap_adjust(arr, end, maxPosition);
    }
}

void build_max_heap(int numbers[],int end){
    for(int i = end/2 ; i>=0; i--){
        heap_adjust(numbers,end,i);
    }
}

void heap_sort(int numbers[],int length){
    int end = length-1;
    do{
        build_max_heap(numbers,end);
        swap(numbers[0],numbers[end]);
        end--;
    }while(end>0);
    
    for (int i = 0; i < length; i++)
    {
        std::cout << numbers[i] << ",";
    }
}

int main()
{
    int numbers[] = {82,37,10,69,1,92,6,13,77,33,47,12,23,82,71,57,58,51,57,75};
    int length;
    GET_LEN(numbers, length);
    heap_sort(numbers,length);
    return 0;
}

写的时候发现好多基本的语法都全忘光了。。
c++的交换，发现用异或来交换可能会导致问题，
比如我想象的过程是

1
2
3
4
5
6
7
8
9

arr[0] = 1 ;
swap(arr[0],arr[0]) ;

a = 1, b=1

a = a ^ b = 0
b = a ^ b = 0 ^ 1 = 1
a = a ^ b = 0 ^ 1 = 1

结果实际执行的是

1
2
3
4
5
6
7

a = 1, b=a

a = a ^ a = 0
b = a ^ a = 0 
a = a ^ a = 0

另外js和python的版本基本都是直接复制的java的逻辑，没有用上它们特色的函数式编程等方式，比如js版本的快排，虽然它要了更多空间，但是js的那种实现明显更‘地道’.