堆排序（递归写法、非递归写法、从下标0开始计数、从下标1开始计数）

下标从1开始计数，非递归写法(1)

# include <iostream>
# include <algorithm>

void sift(int arr[], int start, int end) {
   
    int dad = start;
    int son = dad * 2;
    while (son <= end) {
    
        if (son+1 <= end && arr[son] < arr[son + 1]) {
   	
        	son++;
		}

        if (arr[dad] > arr[son]) {
   	
        	return;
		} else {
   
            std::swap(arr[dad], arr[son]);
            dad = son;
            son = dad * 2;
        }
    }
}

void heap_sort(int arr[], int len) {
   
    for (int i = len / 2; i >= 1; i--) {
   
    	sift(arr, i, len);
	}
        
    for (int i = len; i >= 2; i--) {
   
        std::swap(arr[1], arr[i]);
        sift(arr, 1, i - 1);
    }
}

int main() {
   
	int n;
	std::cin >> n;

	int* arr = new int[n+1];
	
	for (int i = 1; i <= n; i++) {
   
		scanf("%d", &arr[i]);
	}
	
	int len = n;
    heap_sort(arr, len);
    for (int i = 1; i <= len; i++) {
   
    	printf("%d%c", arr[i], " \n"[i==len]);
	}

    delete[] arr;
    
    return 0;
}

下标从1开始计数，非递归写法(2)

# include <iostream>
# include <algorithm>

void sift(int arr[], int start, int end) {
   
	while (start <= end) {
   
	    int dad = start;
    	int son = dad * 2;
    	
		if (son <= end && arr[son] > arr[dad]) {
   
			dad = son;
		}
		
		if (son+1 <= end && arr[son+1] > arr[dad]) {
   
			dad = son + 1;
		}
		
		if (dad != start) {
   
			std::swap(arr[dad], arr[start]);
			start = dad;
		} else {
   
			break;
		}
	}
}

void heap_sort(int arr[], int len) {
   
    for (int i = len / 2; i >= 1; i--) {
   
    	sift(arr, i, len);
	}
    
    for (int i = len; i >= 2; i--) {
   
        std::swap(arr[1], arr[i]);
        sift(arr, 1, i - 1);
    }
}

int main() {
   
	int n;
	std::cin >> n;

	int* arr = new int[n+1];
	
	for (int i = 1; i <= n; i++) {
   
		scanf("%d", &arr[i]);
	}
	
	int len = n;
    heap_sort(arr, len);
    for (int i = 1; i <= len; i++) {
   
    	printf("%d%c", arr[i], " \n"[i==len]);
	}

    delete[] arr;
    
    return 0;
}

下标从1开始计数，递归写法(1)

# include <iostream>
# include <algorithm>

void sift(int arr[], int start, int end) {
   
	int dad = start;
	int son = dad * 2;
		
	if (son <= end) {
   
		if (son+1 <= end && arr[son] < arr[son + 1]) {
   
			son++;
		}

		if (arr[dad] < arr[son]) {
   
			std::swap(arr[dad], arr[son]);
			sift(arr, son, end);
		}
	}
}

void heap_sort(int arr[], int len) {
   
    for (int i = len / 2; i >= 1; i--) {
   
    	sift(arr, i, len);
	}
        
    for (int i = len; i >= 2; i--) {
   
        std::swap(arr[1], arr[i]);
        sift(arr, 1, i - 1);
    }
}

int main() {
   
	int n;
	std::cin >> n;

	int* arr = new int[n+1];
	
	for (int i = 1; i <= n; i++) {
   
		scanf("%d", &arr[i]);
	}
	
	int len = n;
    heap_sort(arr, len);
    for (int i = 1; i <= len; i++) {
   
    	printf("%d%c", arr[i], " \n"[i==len]);
	}

    delete[] arr;
    
    return 0;
}

下标从1开始计数，递归写法(2)

# include <iostream>
# include <algorithm>

void sift(int arr[], int start, int end) {
   
	if (start <= end) {
   
	    int dad = start;
    	int son = dad * 2;
    	
		if (son <= end && arr[son] > arr[dad]) {
   
			dad = son;
		}
		
		if (son+1 <= end && arr[son+1] > arr[dad]) {
   
			dad = son + 1;
		}
		
		if (dad != start) {
   
			std::swap(arr[dad], arr[start]);
			sift(arr, dad, end);
		}
	}
}

void heap_sort(int arr[], int len) {
   
    for (int i = len / 2; i >= 1; i--) {
   
    	sift(arr, i, len);
	}
    
    for (int i = len; i >= 2; i--) {
   
        std::swap(arr[1], arr[i]);
        sift(arr, 1, i - 1);
    }
}

int main() {
   
	int n;
	std::cin >> n;

	int* arr = new int[n+1];
	
	for (int i = 1; i <= n; i++) {
   
		scanf("%d", &arr[i]);
	}
	
	int len = n;
    heap_sort(arr, len);
    for (int i = 1; i <= len; i++) {
   
    	printf("%d%c", arr[i], " \n"[i==len]);
	}

    delete[] arr;
    
    return 0;
}

下标从0开始计数，非递归写法(1)

# include <iostream>
# include <algorithm>

void sift(int arr[], int start, int end) {
   
    int dad = start;
    int son = dad * 2 + 1;
    while (son <= end) {
    
        if (son + 1 <= end && arr[son] < arr[son + 1]) {
   
        	son++;
		}

        if (arr[dad] > arr[son]) {
   	 
        	return;
		} else {
   
            std::swap(arr[dad], arr[son]);
            dad = son;
            son = dad * 2 + 1;
        }
    }
}

void heap_sort(int arr[], int len) {
   
    for (int i = len / 2 - 1; i >= 0; i--) {
   
    	sift(arr, i, len - 1);
	}
        
    for (int i = len - 1; i > 0; i--) {
   
        std::swap(arr[0], arr[i]);
        sift(arr, 0, i - 1);
    }
}

int main() {
   
	int n;
	std::cin >> n;

	int* arr = new int[n];
	
	for (int i = 0; i < n; i++) {
   
		scanf("%d", &arr[i]);
	}
	
	int len = n;
    heap_sort(arr, len);
    for (int i = 0; i < len; i++) {
   
    	printf("%d%c", arr[i], " \n"[i==len-1]);
	}

    delete[] arr;
    
    return 0;
}

下标从0开始计数，非递归写法(2)

# include <iostream>
# include <algorithm>

void sift(int arr[], int start, int end) {
   
	while (start <= end) {
   
	    int dad = start;
    	int son = dad * 2 + 1;
    	
		if (son <= end && arr[son] > arr[dad]) {
   
			dad = son;
		}
		
		if (son+1 <= end && arr[son+1] > arr[dad]) {
   
			dad = son + 1;
		}
		
		if (dad != start) {
   
			std::swap(arr[dad], arr[start]);
			start = dad;
		} else {
   
			break;
		}
	}
}

void heap_sort(int arr[], int len) {
   
    for (int i = len / 2 - 1; i >= 0; i--) {
   
    	sift(arr, i, len - 1);
	}
    
    for (int i = len - 1; i > 0; i--) {
   
        std::swap(arr[0], arr[i]);
        sift(arr, 0, i - 1);
    }
}

int main() {
   
	int n;
	std::cin >> n;

	int* arr = new int[n];
	
	for (int i = 0; i < n; i++) {
   
		scanf("%d", &arr[i]);
	}
	
	int len = n;
    heap_sort(arr, len);
    for (int i = 0; i < len; i++) {
   
    	printf("%d%c", arr[i], " \n"[i==len-1]);
	}

    delete[] arr;
    
    return 0;
}

下标从0开始计数，递归写法(1)

# include <iostream>
# include <algorithm>

void sift(int arr[], int start, int end) {
   
	int dad = start;
	int son = dad * 2 + 1;
		
	if (son <= end) {
   
		if (son+1 <= end && arr[son] < arr[son + 1]) {
   
			son++;
		}

		if (arr[dad] < arr[son]) {
   
			std::swap(arr[dad], arr[son]);
			sift(arr, son, end);
		}
	}
}

void heap_sort(int arr[], int len) {
   
	for (int i = len / 2 - 1; i >= 0; i--) {
   
		sift(arr, i, len - 1);
	}

	for (int i = len - 1; i > 0; i--) {
   
		std::swap(arr[0], arr[i]);
		sift(arr, 0, i - 1);
	}
}

int main() {
   
	int n;
	std::cin >> n;

	int* arr = new int[n];

	for (int i = 0; i < n; i++) {
   
		scanf("%d", &arr[i]);
	}

	int len = n;
	heap_sort(arr, len);
	for (int i = 0; i < len; i++) {
   
		printf("%d%c", arr[i], " \n"[i==len-1]);
	}

	delete[] arr;

	return 0;
}

下标从0开始计数，递归写法(2)

# include <iostream>
# include <algorithm>

void sift(int arr[], int start, int end) {
   
	if (start <= end) {
   
		int dad = start;
		int son = dad * 2 + 1;

		if (son <= end && arr[son] > arr[dad]) {
   
			dad = son;
		}

		if (son+1 <= end && arr[son+1] > arr[dad]) {
   
			dad = son + 1;
		}

		if (dad != start) {
   
			std::swap(arr[dad], arr[start]);
			sift(arr, dad, end);
		}
	}
}

void heap_sort(int arr[], int len) {
   
	for (int i = len / 2 - 1; i >= 0; i--) {
   
		sift(arr, i, len - 1);
	}

	for (int i = len - 1; i > 0; i--) {
   
		std::swap(arr[0], arr[i]);
		sift(arr, 0, i - 1);
	}
}

int main() {
   
	int n;
	std::cin >> n;

	int* arr = new int[n];

	for (int i = 0; i < n; i++) {
   
		scanf("%d", &arr[i]);
	}

	int len = n;
	heap_sort(arr, len);
	for (int i = 0; i < len; i++) {
   
		printf("%d%c", arr[i], " \n"[i==len-1]);
	}

	delete[] arr;

	return 0;
}

测试OJ：（需登录）
https://pintia.cn/problem-sets/15/problems/720