1. AI技术聚合首页
  2. Python

七大排序算法的多语言代码实现

xiaoxingxing • • Python • 阅读 115

文章目录

前言

常用排序算法有冒泡排序、快速排序、插入排序、选择排序、希尔排序、归并排序、堆排序等。

一、排序算法

1.原理简述

1. 冒泡排序

比较相邻的元素，将较大的元素交换至右端。

2. 选择排序

在未排序序列中找到最小（大）元素，存放到排序序列的起始位置。

3. 插入排序

将未排序元素插入到已排序序列中，位置选择正确的位置。

4. 希尔排序

将数组分割成多个子序列，分别进行插入排序。

5. 归并排序

将两个或两个以上的有序序列合并成一个新的有序序列。

6. 快速排序

通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

7. 堆排序

将待排序序列构造成一个大顶堆，此时，整个序列的最大值就是堆顶的根节点。将其与末尾元素进行交换，此时末尾就为最大值。然后将剩余n-1个元素重新构造成一个堆，这样会得到n个元素的次小值。如此反复执行，便能得到一个有序序列了。

2.分类与复杂度

大类算法时间复杂度稳定性
交换排序冒泡排序O(n^2)稳定
快速排序O(nlogn)　
选择排序选择排序O(n^2)　
堆排序O(nlogn)　
插入排序插入排序O(n^2)稳定
希尔排序O(n^(1.3~1.5))　
归并排序归并排序O(nlogn)稳定

二、实例代码

1.冒泡排序

七大排序算法的多语言代码实现

C

void bubble_sort(int arr[], int n) 
{ 
    int i, j; 
    for (i = 0; i < n-1; i++)       
   
       for (j = 0; j < n-i-1; j++)  
           if (arr[j] > arr[j+1]) 
              swap(&arr[j], &arr[j+1]); 
}

Python

def bubble_sort(nums):
    for i in range(len(nums)-1):
        for j in range(len(nums)-i-1):
            if nums[j] > nums[j+1]:
                nums[j], nums[j+1] = nums[j+1], nums[j]
    return nums

Java

public static void bubbleSort(int[] arr) {
    int n = arr.length;
    for (int i = 0; i < n - 1; i++) {
        for (int j = 0; j < n - i - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
    }
}

Golang

func BubbleSort(arr []int) {
	for i := 0; i < len(arr); i++ {
		for j := 0; j < len(arr)-i-1; j++ {
			if arr[j] > arr[j+1] {
				arr[j], arr[j+1] = arr[j+1], arr[j]
			}
		}
	}
}

Rust

fn bubble_sort(arr: &mut [i32]) {
    let len = arr.len();
    for i in 0..len {
        for j in 0..len - i - 1 {
            if arr[j] > arr[j + 1] {
                arr.swap(j, j + 1);
            }
        }
    }
}

Dephi

procedure BubbleSort(var A: array of Integer);
var
  I, J, T: Integer;
begin
  for I := Low(A) to High(A) - 1 do
    for J := I + 1 to High(A) do
      if A[I] > A[J] then
      begin
        T := A[I];
        A[I] := A[J];
        A[J] := T;
      end;
end;

2.选择排序

七大排序算法的多语言代码实现

C

void selection_sort(int arr[], int n) 
{ 
    int i, j, min_idx; 
  
    for (i = 0; i < n-1; i++) 
    { 
        min_idx = i; 
        for (j = i+1; j < n; j++) 
          if (arr[j] < arr[min_idx]) 
            min_idx = j; 
  
        swap(&arr[min_idx], &arr[i]); 
    } 
}

Python

def selection_sort(nums):
    for i in range(len(nums)-1):
        min_index = i
        for j in range(i+1, len(nums)):
            if nums[j] < nums[min_index]:
                min_index = j
        nums[i], nums[min_index] = nums[min_index], nums[i]
    return nums

Java

public static void selectionSort(int[] arr) {
    int n = arr.length;
    for (int i = 0; i < n - 1; i++) {
        int minIndex = i;
        for (int j = i + 1; j < n; j++) {
            if (arr[j] < arr[minIndex]) {
                minIndex = j;
            }
        }
        int temp = arr[i];
        arr[i] = arr[minIndex];
        arr[minIndex] = temp;
    }
}

 Golang

func SelectionSort(arr []int) {
	for i := 0; i < len(arr); i++ {
		minIndex := i
		for j := i + 1; j < len(arr); j++ {
			if arr[j] < arr[minIndex] {
				minIndex = j
			}
		}
		arr[i], arr[minIndex] = arr[minIndex], arr[i]
	}
}

 Rust

fn selection_sort(arr: &mut [i32]) {
    let len = arr.len();
    for i in 0..len {
        let mut min_index = i;
        for j in i + 1..len {
            if arr[j] < arr[min_index] {
                min_index = j;
            }
        }
        arr.swap(i, min_index);
    }
}

 Dephi

procedure SelectionSort(var A: array of Integer);
var
  I, J, Min, T: Integer;
begin
  for I := Low(A) to High(A) - 1 do
  begin
    Min := I;
    for J := I + 1 to High(A) do
      if A[J] < A[Min] then
        Min := J;
    T := A[Min];
    A[Min] := A[I];
    A[I] := T;
  end;
end;

3.插入排序

七大排序算法的多语言代码实现

 

C

void insertion_sort(int arr[], int n) 
{ 
   int i, key, j; 
   for (i = 1; i < n; i++) 
   { 
       key = arr[i]; 
       j = i-1; 
  
       while (j >= 0 && arr[j] > key) 
       { 
           arr[j+1] = arr[j]; 
           j = j-1; 
       } 
       arr[j+1] = key; 
   } 
}

Python

def insertion_sort(nums):
    for i in range(1, len(nums)):
        j = i
        while j > 0 and nums[j] < nums[j-1]:
            nums[j], nums[j-1] = nums[j-1], nums[j]
            j -= 1
    return nums

Java

public static void insertionSort(int[] arr) {
    int n = arr.length;
    for (int i = 1; i < n; i++) {
        int value = arr[i];
        int j = i - 1;
        while (j >= 0 && arr[j] > value) {
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = value;
    }
}

 Golang

func InsertionSort(arr []int) {
	for i := 1; i < len(arr); i++ {
		for j := i; j > 0; j-- {
			if arr[j] < arr[j-1] {
				arr[j], arr[j-1] = arr[j-1], arr[j]
			}
		}
	}
}

 Rust

fn Insertion_sort(arr: &mut [i32]) {
    let len = arr.len();
    for i in 1..len {
        let mut j = i;
        while j > 0 && arr[j] < arr[j - 1] {
            arr.swap(j, j - 1);
            j -= 1;
        }
    }
}

 Dephi

procedure InsertionSort(var A: array of Integer);
var
  I, J, T: Integer;
begin
  for I := Low(A) + 1 to High(A) do
  begin
    T := A[I];
    J := I - 1;
    while (J >= Low(A)) and (A[J] > T) do
    begin
      A[J + 1] := A[J];
      Dec(J);
    end;
    A[J + 1] := T;
  end;
end;

4.希尔排序

七大排序算法的多语言代码实现

C

void Shell_sort(int arr[], int n) 
{ 
    for (int gap = n/2; gap > 0; gap /= 2) 
    { 
        for (int i = gap; i < n; i += 1) 
        { 
            int temp = arr[i]; 
            int j;             
            for (j = i; j >= gap && arr[j - gap] > temp; j -= gap) 
                arr[j] = arr[j - gap]; 
            arr[j] = temp; 
        } 
    } 
}

Python

def shell_sort(nums):
    gap = len(nums) // 2
    while gap > 0:
        for i in range(gap, len(nums)):
            j = i
            while j >= gap and nums[j] < nums[j-gap]:
                nums[j], nums[j-gap] = nums[j-gap], nums[j]
                j -= gap
        gap //= 2
    return nums

Java

public static void shellSort(int[] arr) {
    int n = arr.length;
    for (int gap = n / 2; gap > 0; gap /= 2) {
        for (int i = gap; i < n; i++) {
            int value = arr[i];
            int j = i - gap;
            while (j >= 0 && arr[j] > value) {
                arr[j + gap] = arr[j];
                j -= gap;
            }
            arr[j + gap] = value;
        }
    }
}

 Golang

func ShellSort(arr []int) {
	n := len(arr)
	h := 1
	for h < n/3 {
		h = 3*h + 1
	}
	for h >= 1 {
		for i := h; i < n; i++ {
			for j := i; j >= h && arr[j] < arr[j-h]; j -= h {
				arr[j], arr[j-h] = arr[j-h], arr[j]
			}
		}
		h /= 3
	}
}

 Rust

fn shell_sort(arr: &mut [i32]) {
    let len = arr.len();
    let mut gap = len / 2;
    while gap > 0 {
        for i in gap..len {
            let mut j = i;
            while j >= gap && arr[j - gap] > arr[j] {
                arr.swap(j - gap, j);
                j -= gap;
            }
        }
        gap /= 2;
    }
}

 Dephi

procedure ShellSort(var A: array of Integer);
var
  I, J, T, Gap: Integer;
begin
  Gap := High(A) div 2;
  while Gap > 0 do
  begin
    for I := Gap to High(A) do
    begin
      T := A[I];
      J := I;
      while (J >= Gap) and (A[J - Gap] > T) do
      begin
        A[J] := A[J - Gap];
        J := J - Gap;
      end;
      A[J] := T;
    end;
    Gap := Gap div 2;
  end;
end;

5.归并排序

七大排序算法的多语言代码实现 

C

void merge(int arr[], int l, int m, int r) 
{ 
    int i, j, k; 
    int n1 = m - l + 1; 
    int n2 =  r - m; 
  
    int L[n1], R[n2]; 
  
    for (i = 0; i < n1; i++) 
        L[i] = arr[l + i]; 
    for (j = 0; j < n2; j++) 
        R[j] = arr[m + 1+ j]; 
  
    i = 0; 
    j = 0; 
    k = l; 
    while (i < n1 && j < n2) 
    { 
        if (L[i] <= R[j]) 
        { 
            arr[k] = L[i]; 
            i++; 
        } 
        else
        { 
            arr[k] = R[j]; 
            j++; 
        } 
        k++; 
    } 
  
    while (i < n1) 
    { 
        arr[k] = L[i]; 
        i++; 
        k++; 
    } 
  
    while (j < n2) 
    { 
        arr[k] = R[j]; 
        j++; 
        k++; 
    } 
} 

void merge_sort(int arr[], int l, int r) 
{ 
    if (l < r) 
    { 
        int m = l+(r-l)/2; 
        merge_sort(arr, l, m); 
        merge_sort(arr, m+1, r); 
  
        merge(arr, l, m, r); 
    } 
}

Python

#归并排序：
def merge_sort(nums):
    if len(nums) <= 1:
        return nums
    mid = len(nums) // 2
    left = merge_sort(nums[:mid])
    right = merge_sort(nums[mid:])
    return merge(left, right)

def merge(left, right):
    res = []
    while left and right:
        if left[0] <= right[0]:
            res.append(left.pop(0))
        else:
            res.append(right.pop(0))
    res += left
    res += right
    return res

Java

public static void mergeSort(int[] arr) {
    int n = arr.length;
    if (n < 2) {
        return;
    }
    int mid = n / 2;
    int[] left = new int[mid];
    int[] right = new int[n - mid];
    for (int i = 0; i < mid; i++) {
        left[i] = arr[i];
    }
    for (int i = mid; i < n; i++) {
        right[i - mid] = arr[i];
    }
    mergeSort(left);
    mergeSort(right);
    merge(arr, left, right);
}

public static void merge(int[] arr, int[] left, int[] right) {
    int i = 0, j = 0, k = 0;
    int leftLen = left.length;
    int rightLen = right.length;
    while (i < leftLen && j < rightLen) {
        if (left[i] <= right[j]) {
            arr[k++] = left[i++];
        } else {
            arr[k++] = right[j++];
        }
    }
    while (i < leftLen) {
        arr[k++] = left[i++];
    }
    while (j < rightLen) {
        arr[k++] = right[j++];
    }
}

 Golang

func MergeSort(arr []int) {
	if len(arr) <= 1 {
		return
	}
	mid := len(arr) / 2
	left := arr[:mid]
	right := arr[mid:]
	MergeSort(left)
	MergeSort(right)
	i := 0
	j := 0
	k := 0
	for i < len(left) && j < len(right) {
		if left[i] < right[j] {
			arr[k] = left[i]
			i++
		} else {
			arr[k] = right[j]
			j++
		}
		k++
	}
	for i < len(left) {
		arr[k] = left[i]
		i++
		k++
	}
	for j < len(right) {
		arr[k] = right[j]
		j++
		k++
	}
}

 Rust

fn merge_sort(arr: &mut [i32]) {
    let len = arr.len();
    if len > 1 {
        let mid = len / 2;
        merge_sort(&mut arr[..mid]);
        merge_sort(&mut arr[mid..]);
        merge(arr, mid);
    }
}

fn merge(arr: &mut [i32], mid: usize) {
    let mut left = 0;
    let mut right = mid;
    let mut temp = Vec::with_capacity(arr.len());
    while left < mid && right < arr.len() {
        if arr[left] <= arr[right] {
            temp.push(arr[left]);
            left += 1;
        } else {
            temp.push(arr[right]);
            right += 1;
        }
    }
    while left < mid {
        temp.push(arr[left]);
        left += 1;
    }
    while right < arr.len() {
        temp.push(arr[right]);
        right += 1;
    }
    for i in 0..arr.len() {
        arr[i] = temp[i];
    }
}

 Dephi

procedure MergeSort(var A: array of Integer; Low, High: Integer);
var
  Mid: Integer;
begin
  if Low < High then
  begin
    Mid := (Low + High) div 2;
    MergeSort(A, Low, Mid);
    MergeSort(A, Mid + 1, High);
    Merge(A, Low, Mid, High);
  end;
end;

6.快速排序

七大排序算法的多语言代码实现

 

C

int partition (int arr[], int low, int high) 
{ 
    int pivot = arr[high];   
    int i = (low - 1);  
  
    for (int j = low; j <= high- 1; j++) 
    { 
        if (arr[j] <= pivot) 
        { 
            i++;   
            swap(&arr[i], &arr[j]); 
        } 
    } 
    swap(&arr[i + 1], &arr[high]); 
    return (i + 1); 
} 

void quick_sort(int arr[], int low, int high) 
{ 
    if (low < high) 
    { 
        int pi = partition(arr, low, high); 
        quick_sort(arr, low, pi - 1); 
        quick_sort(arr, pi + 1, high); 
    } 
}

Python

# 快速排序：
def quick_sort(nums):
    if len(nums) <= 1:
        return nums
    pivot = nums[0]
    left = [x for x in nums[1:] if x < pivot]
    right = [x for x in nums[1:] if x >= pivot]
    return quick_sort(left) + [pivot] + quick_sort(right)

Java

public static void quickSort(int[] arr, int low, int high) {
    if (low < high) {
        int pivot = partition(arr, low, high);
        quickSort(arr, low, pivot - 1);
        quickSort(arr, pivot + 1, high);
    }
}

public static int partition(int[] arr, int low, int high) {
    int pivot = arr[high];
    int i = low - 1;
    for (int j = low; j < high; j++) {
        if (arr[j] <= pivot) {
            i++;
            int temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }
    }
    int temp = arr[i + 1];
    arr[i + 1] = arr[high];
    arr[high] = temp;
    return i + 1;
}

 Golang

func QuickSort(arr []int) {
	if len(arr) <= 1 {
		return
	}
	pivot := arr[0]
	left := []int{}
	right := []int{}
	for i := 1; i < len(arr); i++ {
		if arr[i] < pivot {
			left = append(left, arr[i])
		} else {
			right = append(right, arr[i])
		}
	}
	QuickSort(left)
	QuickSort(right)
	arr = append(append(left, pivot), right...)
}

 Rust

fn quick_sort(arr: &mut [i32]) {
    let len = arr.len();
    if len > 1 {
        let pivot = partition(arr);
        quick_sort(&mut arr[..pivot]);
        quick_sort(&mut arr[pivot + 1..]);
    }
}
fn partition(arr: &mut [i32]) -> usize {
    let len = arr.len();
    let pivot = arr[len - 1];
    let mut i = 0;
    for j in 0..len - 1 {
        if arr[j] < pivot {
            arr.swap(i, j);
            i += 1;
        }
    }
    arr.swap(i, len - 1);
}

 Dephi

procedure QuickSort(var A: array of Integer; Low, High: Integer);
var
  I, J, Pivot: Integer;
begin
  if Low < High then
  begin
    Pivot := A[Low];
    I := Low;
    J := High;
    repeat
      while A[I] < Pivot do
        Inc(I);
      while A[J] > Pivot do
        Dec(J);
      if I <= J then
      begin
        Swap(A[I], A[J]);
        Inc(I);
        Dec(J);
      end;
    until I > J;
    if Low < J then
      QuickSort(A, Low, J);
    if I < High then
      QuickSort(A, I, High);
  end;
end;

7.堆排序

七大排序算法的多语言代码实现 

C

void heapify(int arr[], int n, int i) 
{ 
    int largest = i; 
    int l = 2*i + 1; 
    int r = 2*i + 2; 
  
    if (l < n && arr[l] > arr[largest]) 
        largest = l; 
  
    if (r < n && arr[r] > arr[largest]) 
        largest = r; 
  
    if (largest != i) 
    { 
        swap(arr[i], arr[largest]); 
        heapify(arr, n, largest); 
    } 
} 

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

Python

# 堆排序：
def heap_sort(nums):
    n = len(nums)
    for i in range(n//2-1, -1, -1):
        heapify(nums, n, i)
    for i in range(n-1, 0, -1):
        nums[i], nums[0] = nums[0], nums[i]
        heapify(nums, i, 0)
    return nums

def heapify(nums, n, i):
    largest = i
    l = 2*i + 1
    r = 2*i + 2
    if l < n and nums[i] < nums[l]:
        largest = l
    if r < n and nums[largest] < nums[r]:
        largest = r
    if largest != i:
        nums[i], nums[largest] = nums[largest], nums[i]
        heapify(nums, n, largest)

Java

public static void heapSort(int[] arr) {
    int n = arr.length;
    for (int i = n / 2 - 1; i >= 0; i--) {
        heapify(arr, n, i);
    }
    for (int i = n - 1; i >= 0; i--) {
        int temp = arr[0];
        arr[0] = arr[i];
        arr[i] = temp;
        heapify(arr, i, 0);
    }
}

public static void heapify(int[] arr, int n, int i) {
    int largest = i;
    int left = 2 * i + 1;
    int right = 2 * i + 2;
    if (left < n && arr[left] > arr[largest]) {
        largest = left;
    }
    if (right < n && arr[right] > arr[largest]) {
        largest = right;
    }
    if (largest != i) {
        int temp = arr[i];
        arr[i] = arr[largest];
        arr[largest] = temp;
        heapify(arr, n, largest);
    }
}

 Golang

func HeapSort(arr []int) {
	n := len(arr)
	for i := n/2 - 1; i >= 0; i-- {
		heapify(arr, n, i)
	}
	for i := n - 1; i >= 0; i-- {
		arr[0], arr[i] = arr[i], arr[0]
		heapify(arr, i, 0)
	}
}

func heapify(arr []int, n, i int) {
	largest := i
	l := 2*i + 1
	r := 2*i + 2
	if l < n && arr[l] > arr[largest] {
		largest = l
	}
	if r < n && arr[r] > arr[largest] {
		largest = r
	}
	if largest != i {
		arr[i], arr[largest] = arr[largest], arr[i]
		heapify(arr, n, largest)
	}
}

Rust

fn heap_sort(arr: &mut [i32]) {
    let len = arr.len();
    for i in (0..len / 2).rev() {
        heapify(arr, i, len);
    }
    for i in (1..len).rev() {
        arr.swap(0, i);
        heapify(arr, 0, i);
    }
}

fn heapify(arr: &mut [i32], i: usize, len: usize) {
    let mut largest = i;
    let left = 2 * i + 1;
    let right = 2 * i + 2;
    if left < len && arr[left] > arr[largest] {
        largest = left;
    }
    if right < len && arr[right] > arr[largest] {
        largest = right;
    }
    if largest != i {
        arr.swap(i, largest);
        heapify(arr, largest, len);
    }
}

 Dephi

procedure HeapSort(var A: array of Integer);
var
  I, T: Integer;
begin
  BuildHeap(A);
  for I := High(A) downto Low(A) + 1 do
  begin
    T := A[Low(A)];
    A[Low(A)] := A[I];
    A[I] := T;
    Heapify(A, Low(A), I - 1);
  end;
end;

总结

七大排序算法的多语言代码实现

♥️ 作者：Hann Yang

♥️ 主页：CSDN主页

♥️ 2022博客之星Top58，原力榜Top10/作者周榜Top13
♥️ “抢走你工作的不会是 AI ，而是先掌握 AI 能力的人”

文章出处登录后可见！

已经登录？立即刷新

共计人评分，平均分

到目前为止还没有投票！成为第一位评论此文章。

赞 (0)
xiaoxingxing的头像xiaoxingxing管理团队
0
上一篇 2023年3月5日 上午10:44
下一篇 2023年3月5日 上午10:47

相关推荐