排序算法是面试中会经常会被问到的一类问题，如果可以掌握较多的排序算法，在面试过程中才更有机会被面试官看重哦，下面我们准备了一些常见的面试算法，并分别给出了c++和python的代码实现，小伙伴们一起学起来吧！
冒泡排序（Bubble Sort）
基于交换的排序，每次遍历需要排序的元素，依次比较相邻的两个元素的大小，如果前一个元素大于后一个元素则两者交换，保证最后一个数字一定是最大的（假设按照从小到大排序），即最后一个元素已经排好序，下一轮只需要保证前面 n-1 个元素的顺序即可。
之所以称为冒泡，是因为最大/最小的数，每一次都往后面冒，就像是水里面的气泡一样。
排序（假设从小到大）的步骤如下：
- 从头开始，比较相邻的两个数，如果第一个数比第二个数大，那么就交换它们位置。
- 从开始到最后一对比较完成，一轮结束后，最后一个元素的位置已经确定。
- 除了最后一个元素以外，前面的所有未排好序的元素重复前面两个步骤。
- 重复前面 1 ～ 3 步骤，直到所有元素都已经排好序。
冒泡排序c++实现
#include <iostream>
using namespace std;
void bubbleSort(int nums[],int size);
void printf(int nums[],int size);
int main() {
int nums[] = {98,90,34,56,21};
int size = sizeof(nums)/sizeof(nums[0]);
bubbleSort(nums,size);
return 0;
}
void bubbleSort(int nums[],int size) {
// 每轮针对前面（size-i）个数进行排序
for (int i = 0; i < size - 1; i++) {
cout<<"第" << (i + 1) << "轮交换开始" <<endl;
// 每一轮排序，从第 0 个元素，到 size-1-i 个元素
for (int j = 0; j < size - 1 - i; j++) {
// 对比相邻的两个元素
if (nums[j] > nums[j + 1]) {
// 元素交换。使得大的元素在后面
int temp = nums[j + 1];
nums[j + 1] = nums[j];
nums[j] = temp;
}
printf(nums,size);
}
}
}
void printf(int nums[],int size){
for (int i = 0; i < size; i++) {
cout<<nums[i]<<" ";
}
cout<<endl;
}冒泡排序python实现
class Solution:
def bubbleSort(self, nums):
size = len(nums)
# 每轮针对前面（size - i）个数进行排序
for i in range(size):
print("第", (i + 1), "轮交换开始")
for j in range(0, size - 1 - i):
if nums[j] > nums[j + 1]:
nums[j], nums[j + 1] = nums[j + 1], nums[j]
self.printNums(nums)
def printNums(self, nums):
for i in range(len(nums)):
print("%d " % nums[i], end="")
print("")
if __name__ == '__main__':
solution = Solution()
nums = [98, 90, 34, 56, 21]
solution.printNums(nums)
solution.bubbleSort(nums)选择排序
每次选择剩下的元素中最小的那个元素，与当前索引位置的元素交换，直到所有的索引位置都选择完成。
排序的步骤如下：
- 从第一个元素开始，遍历其后面的元素，找出其后面比它更小的且最小的元素，若有，则两者交换，保证第一个元素最小。
- 对第二个元素一样，遍历其后面的元素，找出其后面比它更小的且最小的元素，若存在，则两者交换，保证第二个元素在未排序的数中（除了第一个元素）最小。
- 依次类推，直到最后一个元素，那么数组就已经排好序了。
选择排序c++实现
#include <iostream>
using namespace std;
void selectionSort(int nums[],int size);
void printf(int nums[],int size);
int main() {
int nums[] = {98,90,34,56,21};
int size = sizeof(nums)/sizeof(nums[0]);
printf(nums,size);
selectionSort(nums,size);
return 0;
}
void selectionSort(int nums[],int size) {
int times = 0;
int minIndex;
for (int i = 0; i < size - 1; i++) {
cout<< "第" << (i + 1) << "轮选择开始："<<endl;
minIndex = i;
for (int j = i + 1; j < size; j++) {
times++;
if (nums[j] < nums[minIndex]) {
minIndex = j;
}
}
cout<<"交换 " << nums[i] << "和" << nums[minIndex]<<endl;
int temp = nums[i];
nums[i] = nums[minIndex];
nums[minIndex] = temp;
printf(nums,size);
}
cout<<"比较次数："<< times<<endl;
}
void printf(int nums[],int size){
for (int i = 0; i < size; i++) {
cout<<nums[i]<<" ";
}
cout<<endl;
}选择排序python实现
class Solution:
def selectionSort(self, nums):
times = 0
size = len(nums)
minIndex, temp = 0, 0
for i in range(size - 1):
print("第", (i + 1), "轮选择开始：")
minIndex = i
for j in range(i + 1, size):
times = times + 1
if (nums[j] < nums[minIndex]):
minIndex = j
print("交换 ", nums[i], "和", nums[minIndex])
print(end="")
temp = nums[i]
nums[i] = nums[minIndex]
nums[minIndex] = temp
self.printNums(nums)
print("比较次数：", times, end="")
def printNums(self, nums):
for i in range(len(nums)):
print("%d " % nums[i], end="")
print("")
if __name__ == '__main__':
solution = Solution()
nums = [98, 90, 34, 56, 21]
solution.printNums(nums)
solution.selectionSort(nums)插入排序
依次选择一个元素，插入到前面已经排好序的数组中间，确保它处于正确的位置，当然，这是需要已经排好的顺序数组不断移动。步骤描述如下：
- 从第一个元素开始，可以认为第一个元素已经排好顺序。
- 取出后面一个元素
n，在前面已经排好顺序的数组里从尾部往头部遍历，假设正在遍历的元素为nums[i]，如果num[i]>n，那么将nums[i]移动到后面一个位置，直到找到已经排序的元素小于或者等于新元素的位置，将n放到新腾空出来的位置上。如果没有找到，那么nums[i]就是最小的元素，放在第一个位置。 - 重复上面的步骤 2，直到所有元素都插入到正确的位置。
插入排序c++实现
#include <iostream>
using namespace std;
void insertionSort(int nums[],int size);
void printf(int nums[],int size);
int main() {
int nums[] = {98,90,34,56,21};
int size = sizeof(nums)/sizeof(nums[0]);
printf(nums,size);
insertionSort(nums,size);
return 0;
}
void insertionSort(int nums[],int size) {
if (nums == NULL) {
return;
}
int index, temp;
for (int i = 1; i < size; i++) {
// 当前选择插入的元素前面一个索引值
index = i - 1;
// 当前需要插入的元素
temp = nums[i];
while (index >= 0 && nums[index] > temp) {
nums[index + 1] = nums[index];
index--;
}
// 插入空出来的位置
nums[index + 1] = temp;
cout<<"第" << i << "轮插入结果："<<endl;
printf(nums,size);
}
}
void printf(int nums[],int size){
for (int i = 0; i < size; i++) {
cout<<nums[i]<<" ";
}
cout<<endl;
}插入排序python实现
class Solution:
def insertionSort(self, nums):
if len(nums) == 0:
return
size = len(nums)
index, temp = 0, 0
for i in range(1, size):
# 当前选择插入的元素前面一个索引值
index = i - 1
# 当前需要插入的元素
temp = nums[i]
while index >= 0 and nums[index] > temp:
nums[index + 1] = nums[index]
index = index - 1
# 插入空出来的位置
nums[index + 1] = temp
print("第 %d 轮插入结果：" %i)
self.printNums(nums)
def printNums(self, nums):
for i in range(len(nums)):
print("%d " % nums[i], end="")
print("")
if __name__ == '__main__':
solution = Solution()
nums = [98, 90, 34, 56, 21]
solution.printNums(nums)
solution.insertionSort(nums)希尔排序
希尔排序（Shell's Sort）又称“缩小增量排序”（Diminishing Increment Sort），是插入排序的一种更高效的改进版本，同时该算法是首次冲破 O(
标签：nums,python,self,元素,c++,附带,int,排序,size From： https://blog.csdn.net/weixin_43776107/article/details/140428599