常用的内部排序算法
简单选择排序、直接插入排序和冒泡排序、折半插入排序、希尔排序算法、快速排序算法（递归和非递归）、堆排序
运行结果：
python
输入数据15,5,6,7,8,9,10
[外链图片转存中…(img-60STknHj-1720750359076)]
[外链图片转存中…(img-QWNWapS5-1720750359078)]
[外链图片转存中…(img-fVhvkUVx-1720750359079)]
C语言
输入数据8 6 80 50 40
[外链图片转存中…(img-yKdnpElL-1720750359079)]
[外链图片转存中…(img-MlEA4ULs-1720750359080)]
[外链图片转存中…(img-D81R9SPg-1720750359080)]
代码
Python代码
import tkinter as tk
from tkinter import ttk
class SortAlgorithms:
def __init__(self):
self.comparisons = 0
self.moves = 0
def reset_counters(self):
self.comparisons = 0
self.moves = 0
def bubble_sort(self, arr):
self.reset_counters()
n = len(arr)
for i in range(n):
for j in range(0, n - i - 1):
self.comparisons += 1
if arr[j] > arr[j + 1]:
arr[j], arr[j + 1] = arr[j + 1], arr[j]
self.moves += 1
yield arr[:]
def selection_sort(self, arr):
self.reset_counters()
n = len(arr)
for i in range(n):
min_idx = i
for j in range(i + 1, n):
self.comparisons += 1
if arr[j] < arr[min_idx]:
min_idx = j
arr[i], arr[min_idx] = arr[min_idx], arr[i]
self.moves += 1
yield arr[:]
def insertion_sort(self, arr):
self.reset_counters()
for i in range(1, len(arr)):
key = arr[i]
j = i - 1
while j >= 0 and key < arr[j]:
self.comparisons += 1
arr[j + 1] = arr[j]
self.moves += 1
j -= 1
yield arr[:]
arr[j + 1] = key
self.moves += 1
yield arr[:]
def shell_sort(self, arr):
self.reset_counters()
n = len(arr)
gap = n // 2
while gap > 0:
for i in range(gap, n):
temp = arr[i]
j = i
while j >= gap and arr[j - gap] > temp:
self.comparisons += 1
arr[j] = arr[j - gap]
self.moves += 1
j -= gap
yield arr[:]
arr[j] = temp
self.moves += 1
yield arr[:]
gap //= 2
def quick_sort(self, arr):
self.reset_counters()
def _quick_sort(items, low, high):
if low < high:
pivot_index = self.partition(items, low, high)
yield from _quick_sort(items, low, pivot_index)
yield from _quick_sort(items, pivot_index + 1, high)
yield from _quick_sort(arr, 0, len(arr) - 1)
def partition(self, items, low, high):
pivot = items[(low + high) // 2]
left = low
right = high
while True:
while items[left] < pivot:
left += 1
self.comparisons += 1
while items[right] > pivot:
right -= 1
self.comparisons += 1
if left >= right:
return right
items[left], items[right] = items[right], items[left]
self.moves += 1
def heap_sort(self, arr):
self.reset_counters()
n = len(arr)
def heapify(arr, n, i):
largest = i
l = 2 * i + 1
r = 2 * i + 2
if l < n and arr[largest] < arr[l]:
largest = l
if r < n and arr[largest] < arr[r]:
largest = r
if largest != i:
arr[i], arr[largest] = arr[largest], arr[i]
self.moves += 1
heapify(arr, n, largest)
for i in range(n // 2, -1, -1):
heapify(arr, n, i)
yield arr[:]
for i in range(n - 1, 0, -1):
arr[i], arr[0] = arr[0], arr[i]
self.moves += 1
heapify(arr, i, 0)
yield arr[:]
class App:
def __init__(self, root):
self.root = root
self.root.title("内部排序算法模拟系统")
self.sort_algorithms = SortAlgorithms()
self.create_widgets()
def create_widgets(self):
self.frame = ttk.Frame(self.root, padding="10")
self.frame.grid(row=0, column=0, sticky=(tk.W, tk.E, tk.N, tk.S))
ttk.Label(self.frame, text="输入数据 (用逗号隔开)").grid(row=0, column=0, padx=5, pady=5)
self.data_entry = ttk.Entry(self.frame)
self.data_entry.grid(row=0, column=1, padx=5, pady=5)
ttk.Label(self.frame, text="选择排序算法").grid(row=1, column=0, padx=5, pady=5)
self.algorithm = ttk.Combobox(self.frame, values=[
"冒泡排序", "选择排序", "插入排序", "希尔排序", "快速排序", "堆排序"
])
self.algorithm.grid(row=1, column=1, padx=5, pady=5)
self.algorithm.current(0)
self.sort_btn = ttk.Button(self.frame, text="开始排序", command=self.sort_data)
self.sort_btn.grid(row=2, column=0, columnspan=2, padx=5, pady=5)
self.result_text = tk.Text(self.frame, height=15, width=50)
self.result_text.grid(row=3, column=0, columnspan=2, padx=5, pady=5)
def sort_data(self):
data_str = self.data_entry.get()
data = list(map(int, data_str.split(',')))
algorithm = self.algorithm.get()
self.result_text.delete(1.0, tk.END)
self.result_text.insert(tk.END, f"原始数据: {data}\n")
if algorithm == "冒泡排序":
generator = self.sort_algorithms.bubble_sort(data)
elif algorithm == "选择排序":
generator = self.sort_algorithms.selection_sort(data)
elif algorithm == "插入排序":
generator = self.sort_algorithms.insertion_sort(data)
elif algorithm == "希尔排序":
generator = self.sort_algorithms.shell_sort(data)
elif algorithm == "快速排序":
generator = self.sort_algorithms.quick_sort(data)
elif algorithm == "堆排序":
generator = self.sort_algorithms.heap_sort(data)
for sorted_data in generator:
self.result_text.insert(tk.END, f"排序过程: {sorted_data}\n")
comparisons = self.sort_algorithms.comparisons
moves = self.sort_algorithms.moves
self.result_text.insert(tk.END, f"\n排序结果: {data}\n")
self.result_text.insert(tk.END, f"比较次数: {comparisons}\n")
self.result_text.insert(tk.END, f"移动次数: {moves}\n")
if __name__ == "__main__":
root = tk.Tk()
app = App(root)
root.mainloop()
C语言代码
#include <stdio.h>
#include <stdlib.h>
int comparisons = 0;
int moves = 0;
void reset_counters() {
comparisons = 0;
moves = 0;
}
void print_array(int arr[], int size) {
for (int i = 0; i < size; i++) {
printf("%d ", arr[i]);
}
printf("\n");
}
void bubble_sort(int arr[], int size) {
reset_counters();
for (int i = 0; i < size - 1; i++) {
for (int j = 0; j < size - i - 1; j++) {
comparisons++;
if (arr[j] > arr[j + 1]) {
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
moves++;
print_array(arr, size);
}
}
}
}
void selection_sort(int arr[], int size) {
reset_counters();
for (int i = 0; i < size - 1; i++) {
int min_idx = i;
for (int j = i + 1; j < size; j++) {
comparisons++;
if (arr[j] < arr[min_idx]) {
min_idx = j;
}
}
int temp = arr[min_idx];
arr[min_idx] = arr[i];
arr[i] = temp;
moves++;
print_array(arr, size);
}
}
void insertion_sort(int arr[], int size) {
reset_counters();
for (int i = 1; i < size; i++) {
int key = arr[i];
int j = i - 1;
while (j >= 0 && arr[j] > key) {
comparisons++;
arr[j + 1] = arr[j];
moves++;
j--;
print_array(arr, size);
}
arr[j + 1] = key;
moves++;
print_array(arr, size);
}
}
void shell_sort(int arr[], int size) {
reset_counters();
for (int gap = size / 2; gap > 0; gap /= 2) {
for (int i = gap; i < size; i++) {
int temp = arr[i];
int j;
for (j = i; j >= gap && arr[j - gap] > temp; j -= gap) {
comparisons++;
arr[j] = arr[j - gap];
moves++;
print_array(arr, size);
}
arr[j] = temp;
moves++;
print_array(arr, size);
}
}
}
void quick_sort(int arr[], int left, int right) {
if (left < right) {
int i = left, j = right, pivot = arr[left];
while (i < j) {
while (i < j && arr[j] >= pivot) {
comparisons++;
j--;
}
if (i < j) {
arr[i++] = arr[j];
moves++;
print_array(arr, right - left + 1);
}
while (i < j && arr[i] <= pivot) {
comparisons++;
i++;
}
if (i < j) {
arr[j--] = arr[i];
moves++;
print_array(arr, right - left + 1);
}
}
arr[i] = pivot;
moves++;
print_array(arr, right - left + 1);
quick_sort(arr, left, i - 1);
quick_sort(arr, i + 1, right);
}
}
void