【排序算法 C++和Python实现】选择排序

选择排序

C++

简单选择排序堆排序 python

简单选择排序堆排序

#include 
#define N 10
using namespace std;

void selectSort(int r[], int n)
{
    int i, j, minIndex;
    for (i = 0; i < n - 1; i++) // 排序
    {
        minIndex = i;
        for (j = i + 1; j < n; j++) //找最小值
        {
            if (r[minIndex] > r[j])
            {
                minIndex = j;  // 记录最小值下标
            }
        }
        if (minIndex != i)
        {   
            swap(r[i], r[minIndex]);
        }
    }
}

int main()
{
    int numbers[N] = { 3,2,1,5,6,2,8,6,9,7 };
    selectSort(numbers, N);
    for (int i = 0; i < N; i++)
        cout << numbers[i] << " ";
    cout << "n";
    return 0;
}

#include 
#define N 10
using namespace std;
// 下沉操作
void sink(int r[], int k, int n)
{
	int j;
	while (2 * k + 1 < n)  //如果有左孩子
	{
		j = 2 * k + 1; // 指向左孩子  
		// 如果有右孩子，且右孩子大于左孩子,则指向右孩子
		if (j + 1 < n && r[j] < r[j + 1])j++;
		// 父节点比较大的孩子大，则满足堆
		if (r[k] >= r[j]) break;
		else swap(r[k], r[j]); // 否则父节点与较大孩子交换
		k = j; // k为父节点交换后的位置，继续向下比较
	}
}


void heapSort(int r[], int n)
{
	// 构建初始堆
	for (int i = n / 2 - 1; i >= 0; i--) sink(r, i, n);
	// 堆排序
	while (n > 0)
	{
		// 堆顶和最后一个记录交换，交换后n减1
		swap(r[0], r[n - 1]);
		n--;    // 待排序节点-1
		sink(r, 0, n);  // 堆顶下沉
	}
}
int main()
{
	int numbers[N] = { 3,2,1,5,6,2,8,6,9,7 };
	heapSort(numbers, N);
	for (int i = 0; i < N; i++)
		cout << numbers[i] << " ";
	cout << "n";
	return 0;
}

def select_sort(r, n):
    for i in range(n - 1):
        min_index = i
        for j in range(i + 1, n):
            if r[j] < r[min_index]:
                min_index = j
        if (min_index != i):
            r[i], r[min_index] = r[min_index], r[i]


if __name__ == '__main__':
    r = [3, 2, 1, 5, 6, 2, 8, 6, 9, 7]
    select_sort(r, len(r))
    print(r)

def sink(r, k, n):
    while 2 * k + 1 < n:
        j = 2 * k + 1
        if (j + 1 < n) and (r[j] < r[j + 1]):
            j += 1
        if r[k] < r[j]:
            r[k], r[j] = r[j], r[k]
        else:
            break
        k = j

def heap_sort(r, n):
    # 构建初始堆
    for i in range(int(n / 2) - 1, -1,-1):
        sink(r, i, n)
    while n > 0:
        r[0], r[n - 1] = r[n - 1], r[0]
        n -= 1
        sink(r, 0, n)


if __name__ == '__main__':
    r = [3, 2, 1, 5, 6, 2, 8, 6, 9, 7]
    heap_sort(r, len(r))
    print(r)