[基础算法]排序
|
算法
|
78

1452 字
|
1.2 小时

冒泡排序

  • 基本思想：在待排序的一组数中，将相邻的两个数进行比较，若前面的数比后面的数大就交换两数，否则不交换；如此下去，直至最终完成排序。
  • 假定输入为10个数字，以空格分隔，要求输出为升序
  • CPP
#include <iostream>

using namespace std;

// 假定输入为10个数字，以空格分隔，要求输出为升序

#define MAXSIZE 10

void BubbleSort(int arr[]);

int main()
{

    int arr[MAXSIZE];

    for (int i = 0; i < MAXSIZE; i++)
    {
        cin >> arr[i];
    }

    BubbleSort(arr);

    for (int i = 0; i < MAXSIZE; i++)
    {
        cout << arr[i] << " ";
    }

    return 0;
}

void BubbleSort(int arr[])
{
    for (int i = 0; i < MAXSIZE - 1; i++)
    {
        for (int j = 0; j < MAXSIZE - 1 - i; j++)
        {
            if (arr[j] > arr[j + 1])
            {
                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
    }
}
  • Java
import java.util.Scanner;

public class BubbleSort {
    // 假定输入为10个数字，以空格分隔，要求输出为升序
    public static int MAXSIZE = 10;

    public static void main(String[] args) {
        int[] arr = new int[MAXSIZE];
        Scanner sc = new Scanner(System.in);
        for (int i = 0; i < MAXSIZE; i++) {
            arr[i] = sc.nextInt();
        }

        BubbleSortMethod(arr);

        for (int i = 0; i < MAXSIZE; i++) {
            System.out.print(arr[i] + " ");
        }

    }

    public static void BubbleSortMethod(int[] arr) {
        for (int i = 0; i < MAXSIZE - 1; i++) {
            for (int j = 0; j < MAXSIZE - 1 - i; j++) {
                if (arr[j] > arr[j + 1]) {
                    int temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                }
            }
        }
    }
}
  • Python
# 假定输入为10个数字，以空格分隔，要求输出为升序
number_string = input()
string_list = number_string.split()

array = [int(number) for number in string_list]

def bubble_sort(array):
    for i in range(0, 9):
        for j in range(0, 9 - i):
            if array[j] > array[j + 1]:
                temp = array[j]
                array[j] = array[j + 1]
                array[j + 1] = temp

bubble_sort(array)
print(array)

选择排序

  • 基本思想：第一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，然后再从剩余的未排序元素中寻找到最小（大）元素，然后放到已排序的序列的末尾。以此类推，直到全部待排序的数据元素的个数为零。
  • 假定输入为10个数字，以空格分隔，要求输出为升序
  • CPP
#include <iostream>

using namespace std;

 // 假定输入为10个数字，以空格分隔，要求输出为升序

#define MAXSIZE 10

void SelectionSort(int arr[]);

int main()
{
    int arr[MAXSIZE];
    for (int i = 0; i < MAXSIZE; i++)
    {
        cin >> arr[i];
    }

    SelectionSort(arr);

    for (int i = 0; i < MAXSIZE; i++)
    {
        cout << arr[i] << " ";
    }
}

void SelectionSort(int arr[])
{
    for (int i = 0; i < MAXSIZE - 1; i++)
    {
        int min_index = i;
        for (int j = i; j < MAXSIZE; j++)
        {
            if (arr[j] < arr[min_index])
            {
                min_index = j;
            }
        }
        int temp = arr[i];
        arr[i] = arr[min_index];
        arr[min_index] = temp;
    }
}
  • Java
import java.util.Scanner;

public class SelectionSort {
		// 假定输入为10个数字，以空格分隔，要求输出为升序
    public static int MAXSIZE = 10;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int[] arr = new int[MAXSIZE];
        for (int i = 0; i < MAXSIZE; i++) {
            arr[i] = sc.nextInt();
        }

        SelectionSortMethod(arr);

        for (int i = 0; i < MAXSIZE; i++) {
            System.out.print(arr[i] + " ");
        }
    }

    public static void SelectionSortMethod(int[] arr) {
        for (int i = 0; i < MAXSIZE; i++) {
            int minIndex = i;
            for (int j = i + 1; j < MAXSIZE; j++) {
                if (arr[j] < arr[minIndex]) {
                    minIndex = j;
                }
            }
            int temp = arr[minIndex];
            arr[minIndex] = arr[i];
            arr[i] = temp;
        }
    }
}
  • Python
# 假定输入为10个数字，以空格分隔，要求输出为升序
number_string = input()
string_list = number_string.split()

array = [int(number) for number in string_list]

def selection_sort(array):
    for i in range(0, 9):
        min_index = i
        for j in range(i, 10):
            if array[j] < array[min_index]:
                min_index = j
        temp = array[i]
        array[i] = array[min_index]
        array[min_index] = temp

selection_sort(array)
print(array)

插入排序

  • 基本思想：将一个记录插入到已经排好序的有序表中，从而变成一个新的、记录数增1的有序表。在其实现过程使用双层循环，外层循环对除了第一个元素之外的所有元素，内层循环对当前元素前面有序表进行待插入位置查找，并进行移动。
  • 假定输入为10个数字，以空格分隔，要求输出为升序
  • CPP
#include <iostream>

using namespace std;

// 假定输入为10个数字，以空格分隔，要求输出为升序

#define MAXSIZE 10

void InsertionSort(int arr[]);

int main()
{
    int arr[MAXSIZE];
    for (int i = 0; i < MAXSIZE; i++)
    {
        cin >> arr[i];
    }

    InsertionSort(arr);

    for (int i = 0; i < MAXSIZE; i++)
    {
        cout << arr[i] << " ";
    }
}

void InsertionSort(int arr[])
{
    for (int i = 1; i < MAXSIZE; i++)
    {
        int index = i;
        int temp = arr[i];
        for (int j = index - 1; index > 0; j--)
        {
            if (arr[index] < arr[j])
            {
                arr[index] = arr[j];
                arr[j] = temp;
                index--;
            }
            else
            {
                break;
            }
        }
    }
}
  • Java
import java.util.Scanner;

public class InsertionSort {
    // 假定输入为10个数字，以空格分隔，要求输出为升序
    public static int MAXSIZE = 10;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int[] arr = new int[MAXSIZE];
        for (int i = 0; i < MAXSIZE; i++) {
            arr[i] = sc.nextInt();
        }

        InsertionSortMethod(arr);

        for (int i = 0; i < MAXSIZE; i++) {
            System.out.print(arr[i] + " ");
        }
    }

    public static void InsertionSortMethod(int[] arr) {
        for (int i = 0; i < MAXSIZE; i++) {
            int index = i;
            int temp = arr[i];
            for (int j = index - 1; index > 0; j--) {
                if (arr[index] < arr[j]) {
                    arr[index] = arr[j];
                    arr[j] = temp;
                    index--;
                } else {
                    break;
                }
            }
        }
    }
}
  • Python
# 假定输入为10个数字，以空格分隔，要求输出为升序
number_string = input()
string_list = number_string.split()

array = [int(number) for number in string_list]

def insertion_sort(array):
    for i in range(1, len(array)):
        index = i
        temp = array[i]
        while index > 0 and array[index - 1] > temp:
            array[index] = array[index - 1]
            index = index - 1
        array[index] = temp

insertion_sort(array)
print(array)

希尔排序

  • 基本思想：把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至 1 时，整个文件恰被分成一组，算法便终止。
  • 假定输入为10个数字，以空格分隔，要求输出为升序
  • CPP
#include <iostream>

using namespace std;

// 假定输入为10个数字，以空格分隔，要求输出为升序

#define MAXSIZE 10

void ShellSort(int arr[]);

int main()
{
    int arr[MAXSIZE];
    for (int i = 0; i < MAXSIZE; i++)
    {
        cin >> arr[i];
    }

    ShellSort(arr);

    for (int i = 0; i < MAXSIZE; i++)
    {
        cout << arr[i] << " ";
    }
}

void ShellSort(int arr[])
{
    int group = MAXSIZE;
    while (group > 0)
    {
        for (int i = group; i < MAXSIZE; i++)
        {
            int temp = arr[i];
            int j = i;
            while (j >= group && arr[j - group] > temp)
            {
                arr[j] = arr[j - group];
                j -= group;
                arr[j] = temp;
            }
        }
        group /= 2;
    }
}
  • Java
import java.util.Scanner;

public class ShellSort {
    // 假定输入为10个数字，以空格分隔，要求输出为升序
    public static int MAXSIZE = 10;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int[] arr = new int[MAXSIZE];
        for (int i = 0; i < MAXSIZE; i++) {
            arr[i] = sc.nextInt();
        }

        ShellSortMethod(arr);

        for (int i = 0; i < MAXSIZE; i++) {
            System.out.print(arr[i] + " ");
        }
    }

    public static void ShellSortMethod(int[] arr) {
        int group = MAXSIZE;
        while (group > 0) {
            for (int i = group; i < MAXSIZE; i++) {
                int temp = arr[i];
                int j = i;
                while (j >= group && arr[j - group] > temp) {
                    arr[j] = arr[j - group];
                    j -= group;
                    arr[j] = temp;
                }
            }
            group /= 2;
        }
    }
}
  • Python
# 假定输入为10个数字，以空格分隔，要求输出为升序
number_string = input()
string_list = number_string.split()
array = [int(number) for number in string_list]

def shell_sort(array):
    group = len(array) // 2
    while group > 0:
        for i in range(group, len(array)):
            temp = array[i]
            j = i
            while j >= group and array[j - group] > temp:
                array[j] = array[j - group]
                j -= group
            array[j] = temp
        group //= 2

shell_sort(array)
print(array)

归并排序

  • 基本思想：采用分治法（Divide and Conquer），将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。
  • 假定输入为10个数字，以空格分隔，要求输出为升序
  • CPP
#include <iostream>

using namespace std;

// 假定输入为10个数字，以空格分隔，要求输出为升序

#define MAXSIZE 10
int result[MAXSIZE];

void MergeSort(int arr[], int left, int right);
void Merge(int arr[], int left, int mid, int right);

int main()
{
    int arr[MAXSIZE];
    for (int i = 0; i < MAXSIZE; i++)
    {
        cin >> arr[i];
    }

    MergeSort(arr, 0, MAXSIZE - 1);

    for (int i = 0; i < MAXSIZE; i++)
    {
        cout << arr[i] << " ";
    }

    return 0;
}

void MergeSort(int arr[], int left, int right)
{
    if (left < right)
    {
        int mid = left + (right - left) / 2;
        MergeSort(arr, left, mid);
        MergeSort(arr, mid + 1, right);
        Merge(arr, left, mid, right);
    }
}

void Merge(int arr[], int left, int mid, int right)
{
    int i = left, j = mid + 1, k = 0;

    // 合并两个部分
    while (i <= mid && j <= right)
    {
        if (arr[i] <= arr[j])
        {
            result[k++] = arr[i++];
        }
        else
        {
            result[k++] = arr[j++];
        }
    }

    // 处理剩余的元素
    while (i <= mid)
    {
        result[k++] = arr[i++];
    }

    while (j <= right)
    {
        result[k++] = arr[j++];
    }

    // 将合并后的数组复制回原数组
    for (i = 0; i < k; i++)
    {
        arr[left + i] = result[i];
    }
}
  • Java
import java.util.Scanner;

public class MergeSort {
    // 假定输入为10个数字，以空格分隔，要求输出为升序
    public static int MAXSIZE = 10;
    public static int[] result = new int[MAXSIZE];

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int[] arr = new int[MAXSIZE];
        for (int i = 0; i < MAXSIZE; i++) {
            arr[i] = sc.nextInt();
        }

        MergeSortMethod(arr, 0, arr.length - 1);

        for (int i = 0; i < MAXSIZE; i++) {
            System.out.print(arr[i] + " ");
        }
    }

    public static void MergeSortMethod(int[] arr, int left, int right) {
        if (left < right) {
            int mid = (left + right) / 2;
            MergeSortMethod(arr, left, mid);
            MergeSortMethod(arr, mid + 1, right);
            MergeMethod(arr, left, mid, right);
        }
    }

    public static void MergeMethod(int[] arr, int left, int mid, int right) {
        int i = left, j = mid + 1, k = 0;

        // 合并两个部分
        while (i <= mid && j <= right) {
            if (arr[i] <= arr[j]) {
                result[k++] = arr[i++];
            } else {
                result[k++] = arr[j++];
            }
        }

        // 处理剩余的元素
        while (i <= mid) {
            result[k++] = arr[i++];
        }

        while (j <= right) {
            result[k++] = arr[j++];
        }

        // 将合并后的数组复制回原数组
        for (i = 0; i < k; i++) {
            arr[left + i] = result[i];
        }
    }
}
  • Python
# 假定输入为10个数字，以空格分隔，要求输出为升序
number_string = input()
string_list = number_string.split()
array = [int(number) for number in string_list]

def merge_sort(array):
    if(len(array) > 1):
        mid = len(array) // 2
        left_half = array[:mid]
        right_half = array[mid:]

        merge_sort(left_half)
        merge_sort(right_half)

        i, j, k = 0, 0, 0
        while(i < len(left_half) and j < len(right_half)):
            if left_half[i] <= right_half[j]:
                array[k] = left_half[i]
                i = i + 1
            else:
                array[k] = right_half[j]
                j = j + 1
            k = k + 1
    
        while(i < len(left_half)):
            array[k] = left_half[i]
            i = i + 1
            k = k + 1
    
        while(j < len(right_half)):
            array[k] = right_half[j]
            j = j + 1
            k = k + 1

merge_sort(array)
print(array)

快速排序

  • 基本思想：快速排序采用的是分治思想，即在一个无序的序列中选取一个任意的基准元素pivot，利用pivot将待排序的序列分成两部分，前面部分元素均小于或等于基准元素，后面部分均大于或等于基准元素，然后采用递归的方法分别对前后两部分重复上述操作，直到将无序序列排列成有序序列。
  • 假定输入为10个数字，以空格分隔，要求输出为升序
  • CPP
#include <iostream>

using namespace std;

// 假定输入为10个数字，以空格分隔，要求输出为升序

#define MAXSIZE 10

void Quicksort(int arr[], int l, int r);

int main()
{
    int arr[MAXSIZE];
    for (int i = 0; i < MAXSIZE; i++)
    {
        cin >> arr[i];
    }

    Quicksort(arr, 0, MAXSIZE - 1);

    for (int i = 0; i < MAXSIZE; i++)
    {
        cout << arr[i] << " ";
    }

    return 0;
}

void Quicksort(int arr[], int l, int r)
{
    if (l < r)
    {
        int i = l;      // 左指针
        int j = r;      // 右指针
        int x = arr[l]; // 基准
        while (i < j)
        {
            while (i < j && arr[j] > x)
            {
                j--;
            }
            if (i < j)
            {
                arr[i++] = arr[j];

            }
            while (i < j && arr[i] < x)
            {
                i++;
            }
            if (i < j)
            {
                arr[j--] = arr[i];
            }
        }
        arr[i] = x;
        Quicksort(arr, l, i - 1);
        Quicksort(arr, i + 1, r);
    }
}
  • Java
import java.util.Scanner;

public class QuickSort {
    // 假定输入为10个数字，以空格分隔，要求输出为升序
    public static int MAXSIZE = 10;
    public static int[] result = new int[MAXSIZE];

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int[] arr = new int[MAXSIZE];
        for (int i = 0; i < MAXSIZE; i++) {
            arr[i] = sc.nextInt();
        }

        QuickSortMethod(arr, 0, arr.length - 1);

        for (int i = 0; i < MAXSIZE; i++) {
            System.out.print(arr[i] + " ");
        }
    }

    public static void QuickSortMethod(int[] arr, int l, int r) {
        if (l < r) {
            int i = l;      // 左指针
            int j = r;      // 右指针
            int x = arr[l]; // 基准
            while (i < j) {
                while (i < j && arr[j] > x) {
                    j--;
                }
                if (i < j) {
                    arr[i++] = arr[j];

                }
                while (i < j && arr[i] < x) {
                    i++;
                }
                if (i < j) {
                    arr[j--] = arr[i];
                }
            }
            arr[i] = x;
            QuickSortMethod(arr, l, i - 1);
            QuickSortMethod(arr, i + 1, r);
        }
    }
}
  • Python
# 假定输入为10个数字，以空格分隔，要求输出为升序
number_string = input()
string_list = number_string.split()
array = [int(number) for number in string_list]

def quick_sort(array, l, r):
    if l < r:
        i = l; j = r; x = array[i]
        while i < j:
            while i < j and array[j] > x:
                j = j - 1
            if i < j:
                array[i] = array[j]
                i = i + 1
            while i < j and array[i] < x:
                i = i + 1
            if i < j:
                array[j] = array[i]
                j = j - 1

        array[i] = x
        quick_sort(array, l, i - 1)
        quick_sort(array, i + 1, r)

quick_sort(array, 0, len(array) - 1)
print(array)
本人邮箱：yhyshiroha123@outlook.jp
cppJavapython基础算法排序
暂无评论

发送评论 编辑评论 


				

			

						

				

					

						

							

								
							

							
						

					

				

				

					

						

							

								
							

							
						

					

				

				

					

						

							

								
							

							
							
													

					

				

			

			
			

				

					
				

			

				

											

							
							
						

																

							
							
						

																

							
							
						

										
					
											
						

	

		
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
（╯‵□′）╯︵┴─┴
￣﹃￣
(/ω＼)
∠( ᐛ 」∠)＿
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ｀)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ(￣∇￣o)
ヾ(´･ ･｀｡)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò｡)
Σ(っ °Д °;)っ
( ,,´･ω･)ﾉ"(´っω･｀｡)
╮(╯▽╰)╭
o(*////▽////*)q
＞﹏＜
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
	

	

		
颜文字
Emoji
小恐龙
花!
	


									

			

			
			
		

	






上一篇
下一篇 

                    

                    
			        推荐文章
		            

		            

							
[Java EE] Java + MySQL

							
							

							
[Java EE] Spring Boot项目基础

							
							

							
[Java EE] Vue

							
							

							
如何将python文件打包成exe文件

							
							

							
仿射密码

							
							

							
[基础算法]二分

							
							

							
八数码难题

							
							

							
[基础算法]递推与递归