给定一个长度为 n 的数组，请你编写一个函数，返回该数组按升序排序后的结果。
数据范围： 
，数组中每个元素都满足 
要求：时间复杂度 )
，空间复杂度 )
进阶：时间复杂度 )
，空间复杂度
注：本题数据范围允许绝大部分排序算法，请尝试多种排序算法的实现。
[编程题]排序
采用冒泡排序
//表达式求值
#include<stdio.h>
#include <stdlib.h>
int main(){
int a[5];
for (int i = 0; i < 5; i++)
{
scanf("%d",&a[i]);
}
//冒泡排序
for (int i =0; i<5; i++)//决定第几层排序
{
for (int j =0; j<=4-i; j++)
{
if (a[j]>a[j+1])
{
int l=a[j];
a[j]=a[j+1];
a[j+1]=l;
}
}
}
for (int i = 0; i < 5; i++)
{
printf("%d ",a[i]);
}
}
发表于 2024-04-13 12:35:46
回复(1)
int* MySort(int* arr, int arrLen, int* returnSize)
{
int i = 0;
int j = 0;
int flag = 0;
for (i = 0; i < arrLen - 1; i++)
{
flag = 1;
for (j = 0; j < arrLen - i - 1; j++)
{
if (arr[j] > arr[j + 1])
{
arr[j] ^= arr[j + 1];
arr[j + 1] ^= arr[j];
arr[j] ^= arr[j + 1];
flag = 0;
}
}
if (flag)
{
break;
}
}
*returnSize = arrLen;
return arr;
}
编辑于 2024-03-24 14:59:40
回复(0)
void swap(int* a,int* b)
{
int temp;
temp=*a;
*a=*b;
*b=temp;
}
void BubbleSort(int* a, int n)
{
int i,j,flag=0;
for(i=0;i<n-1;i++)
{
flag=0;
for(j=0;j<n-i-1;j++)
{
if(a[j]>a[j+1])
{
swap(&a[j],&a[j+1]);
flag=1;
}
}
if(flag==0)
{
break;
}
}
}
void SelctSort(int* a,int n)
{
int i,j,key;
for(i=0;i<n-1;i++)
{
key=i;
for(j=i+1;j<n;j++)
{
if(a[key]>a[j])
{
key=j;
}
}
if(key!=i)
{
swap(&a[i],&a[key]);
}
}
}
void SelctSortPro(int* a,int n)
{
int i,j;
int begin=0,end=n-1;
int maxi=end,mini=begin;
while(begin<end)
{
i=begin;
j=end;
maxi=end;
mini=begin;
while(i<=end)
{
if(a[maxi]<a[i])
{
maxi=i;
}
if(a[mini]>a[i])
{
mini=i;
}
i++;
}
swap(&a[begin],&a[mini]);
if(maxi==begin)
{
maxi=mini;
}
swap(&a[end],&a[maxi]);
begin++;
end--;
}
}
void InsertSort(int* a,int n)
{
int i,j,temp;
for(i=0;i<n-1;i++)
{
temp=a[i+1];
j=i;
while(j>=0)
{
if(temp<a[j])
{
a[j+1]=a[j];
}
else
{
break;
}
j--;
}
a[j+1]=temp;
}
}
void ShellSort(int* a,int n)
{
int gap=n;
int temp,i,j;
while(gap>1)
{
gap=gap/2;
for(i=0;i<n-gap;i++)
{
temp=a[i+gap];
j=i;
while(j>=0)
{
if(temp<a[j])
{
a[j+gap]=a[j];
j-=gap;
}
else
{
break;
}
}
a[j+gap]=temp;
}
}
}
void QuickSort1(int* a,int begin,int end)
{
if(begin>=end)
{
return;
}
int left=begin,right=end;
int key=begin;
while(left<right)
{
while(a[right]>=a[key]&&right>left)
{
right--;
}
while(a[left]<=a[key]&&right>left)
{
left++;
}
if(left<right)
swap(&a[left],&a[right]);
}
swap(&a[key],&a[left]);
QuickSort1(a,begin,left-1);
QuickSort1(a,left+1,end);
}
void QuickSort2(int* a,int begin,int end)
{
if(begin>=end)
{
return ;
}
int curi=begin;
int temp=a[begin];
int left=begin,right=end;
while(left<right)
{
while(a[right]>=temp&&left<right)
{
right--;
}
a[curi]=a[right];
curi=right;
while(a[left]<=temp&&left<right)
{
left++;
}
a[curi]=a[left];
curi=left;
}
a[curi]=temp;
QuickSort2(a,begin,left-1);
QuickSort2(a,left+1,end);
}
void QuickSort3(int* a,int begin,int end)
{
if(begin>end)
{
return ;
}
int prev=begin,cur=prev+1;
int key=begin;
while(cur<=end)
{
if(a[cur]<=a[key])
{
prev++;
if(cur!=prev)
{
swap(&a[prev],&a[cur]);
}
}
cur++;
}
swap(&a[begin],&a[prev]);
QuickSort3(a,begin,prev-1);
QuickSort3(a,prev+1,end);
}
typedef int StackDataType;
typedef struct StackNode
{
StackDataType data;
struct StackNode* next;
}StackNode;
typedef struct Stack
{
StackNode* q;
int size;
}Stack;
void StackInit(Stack* s)
{
StackNode* head=(StackNode*)malloc(sizeof(StackNode));
head->next=NULL;
s->q=head;
s->size=0;
}
void StackPush(Stack* s,StackDataType x)
{
StackNode* newnode=(StackNode*)malloc(sizeof(StackNode));
newnode->data=x;
newnode->next=s->q->next;
s->q->next=newnode;
s->size++;
}
int StackEmpty(Stack* s)
{
if(s->q->next==NULL)
{
return 1;
}
return 0;
}
StackDataType StackTop(Stack* s)
{
if(!StackEmpty(s))
{
return s->q->next->data;
}
else
{
return -1;
}
}
void StackPop(Stack* s)
{
if(!StackEmpty(s))
{
StackNode* temp=s->q->next;
s->q->next=s->q->next->next;
free(temp);
s->size--;
}
}
int get_mid(int *a,int begin,int end)
{
int left=begin;
int right=end;
int key=begin;
while(left<right)
{
while(a[right]>=a[key]&&left<right)
{
right--;
}
while(a[left]<=a[key]&&left<right)
{
left++;
}
swap(&a[right],&a[left]);
}
swap(&a[key],&a[left]);
return left;
}
void QuickSort4(int* a,int begin,int end)
{
Stack s;
StackInit(&s);
StackPush(&s,end);
StackPush(&s,begin);
int left,mid,right;
while(!StackEmpty(&s))
{
left=StackTop(&s);
StackPop(&s);
right=StackTop(&s);
StackPop(&s);
if(left<right)
{
mid=get_mid(a,left,right);
}
if(left<mid-1)
{
StackPush(&s,mid-1);
StackPush(&s,left);
}
if(right>mid+1)
{
StackPush(&s,right);
StackPush(&s,mid+1);
}
}
}
void MergeSortFun(int* a,int* temp,int begin,int end)
{
if(begin>=end)
{
return ;
}
int mid=(begin+end)/2;
MergeSortFun(a, temp, begin, mid);
MergeSortFun(a, temp, mid + 1, end);
int begin1 = begin;
int end1 = mid;
int begin2 = mid + 1;
int end2 = end;
int i = begin;
while(begin1<=end1&&begin2<=end2)
{
if(a[begin1]<a[begin2])
{
temp[i++]=a[begin1++];
}
else
{
temp[i++]=a[begin2++];
}
}
while(begin1<=end1)
{
temp[i++]=a[begin1++];
}
while(begin2<=end2)
{
temp[i++]=a[begin2++];
}
for(i=begin;i<=end;i++)
{
a[i]=temp[i];
}
}
void MergeSort(int* a,int n)
{
int begin=0;
int end=n-1;
int* temp=(int*)malloc(sizeof(int)*n);
MergeSortFun(a,temp,begin,end);
free(temp);
}
void mergesortnr(int* a, int* temp, int begin, int mid, int end)
{
int head1 = begin;
int tail1 = mid;
int head2 = mid + 1;
int tail2 = end;
int i = begin;
while (head1 <= tail1 && head2 <= tail2)
{
if (a[head1] < a[head2])
{
temp[i++] = a[head1++];
}
else
{
temp[i++] = a[head2++];
}
}
while (head1 <= tail1)
{
temp[i++] = a[head1++];
}
while (head2 <= tail2)
{
temp[i++] = a[head2++];
}
memcpy(a + begin, temp + begin, sizeof(int) * (end - begin + 1));
}
void mergeSort(int *a, int n)
{
int* temp = (int*)malloc(sizeof(int) * n);
int gap = 1;
for (gap = 1; gap < n; gap *= 2)
{
for (int i = 0; i < n - gap; i += 2 * gap)
{
int begin = i;
int end = i + 2 * gap - 1 >= n ? n - 1 : i + 2 * gap - 1;
int mid = i + gap - 1;
mergesortnr(a, temp, begin, mid, end);
}
}
}
int* MySort(int* arr, int arrLen, int* returnSize ) {
mergeSort(arr,arrLen);
*returnSize=arrLen;
return arr;
}
发表于 2024-01-17 19:05:37
回复(0)
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
* 将给定数组排序
* @param arr int整型一维数组 待排序的数组
* @param arrLen int arr数组长度
* @return int整型一维数组
* @return int* returnSize 返回数组行数
*/
int* MySort(int* arr, int arrLen, int* returnSize ) {
// write code here
// int i,j,k;
// for(i=0;i<arrLen;i++)
// {
// for(j=0;j<arrLen-1;j++)
// {
// if(arr[j]>arr[j+1])
// {
// k=arr[j];
// arr[j]=arr[j+1];
// arr[j+1]=k;
// }
// }
// }
int i,j,k,min;
for(i=0;i<arrLen;i++)
{
min=i;
for(j=i;j<arrLen;j++)
{
if(arr[min]>arr[j])
min=j;
}
k=arr[min];
arr[min]=arr[i];
arr[i]=k;
}
* returnSize =arrLen;
return arr;
}
发表于 2023-03-15 05:24:03
回复(2)
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
* 将给定数组排序
* @param arr int整型一维数组 待排序的数组
* @param arrLen int arr数组长度
* @return int整型一维数组
* @return int* returnSize 返回数组行数
*/
int* MySort(int* arr, int arrLen, int* returnSize ) {
// write code here
int j,i;
for(i=0;i<arrLen;i++)
{
for(j=i+1;j<arrLen;j++)
{
if(*(arr+i)>*(arr+j))
{
int t=*(arr+i);
*(arr+i)=*(arr+j);
*(arr+j)=t;
}
}
}
*returnSize=arrLen;
return arr;
}
发表于 2022-11-20 12:23:12
回复(0)
C语言，快排，挖坑法，无优化
void swap(int* a, int* b)
{
int temp = *a;
*a = *b;
*b = temp;
}
void QuickSort(int* arr, int begin, int end)
{
if (begin >= end)
return;
int left = begin, right = end;
int key = arr[left];
int pit=left;
while(left<right)
{
while(left<right&&arr[right]>=key)
{
right--;
}
arr[pit]=arr[right];
pit=right;
while(left<right&&arr[left]<key)
{
left++;
}
arr[pit]=arr[left];
pit=left;
}
pit = left;
arr[pit] = key;
QuickSort(arr, begin, pit-1);
QuickSort(arr, pit+1, end);
}
int* MySort(int* arr, int arrLen, int* returnSize)
{
// write code here
QuickSort(arr, 0, arrLen - 1);
*returnSize = arrLen;
return arr;
}
发表于 2022-07-07 12:36:32
回复(0)
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
* 将给定数组排序
* @param arr int整型一维数组 待排序的数组
* @param arrLen int arr数组长度
* @return int整型一维数组
* @return int* returnSize 返回数组行数
*
* C语言声明定义全局变量请加上static，防止重复定义
*/
int* MySort(int* arr, int arrLen, int* returnSize ) {
// write code here
//冒泡排序
for(int i=0;i<arrLen-1;i++)
for(int j=0;j<arrLen-1-i;j++)
{
if(arr[j+1]<arr[j])
{
int c=arr[j];
arr[j]=arr[j+1];
arr[j+1]=c;
}
}
*returnSize=arrLen;
return arr;
}
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
* 将给定数组排序
* @param arr int整型一维数组 待排序的数组
* @param arrLen int arr数组长度
* @return int整型一维数组
* @return int* returnSize 返回数组行数
*
* C语言声明定义全局变量请加上static，防止重复定义
*/
int* MySort(int* arr, int arrLen, int* returnSize ) {
// write code here
//冒泡排序
for(int i=0;i<arrLen-1;i++)
for(int j=0;j<arrLen-1-i;j++)
{
if(arr[j+1]<arr[j])
{
int c=arr[j];
arr[j]=arr[j+1];
arr[j+1]=c;
}
}
*returnSize=arrLen;
return arr;
}
发表于 2022-05-17 14:34:27
回复(0)
void swap(int *arr,int i,int j)
{
int tem = arr[i];
arr[i] = arr[j];
arr[j] = tem;
}
void heap(int *arr,int index,int heapsize)
{
if(index == heapsize)
return;
else
{
while(index<heapsize)
{
int tem = index;
while(arr[tem]>arr[(tem-1)/2])
{
swap(arr,tem,(tem-1)/2);
tem = (tem-1)/2;
}
index++;
}
}
}
void heapify(int *arr,int index,int heapsize)
{
int left = 2*index+1;
if(left == heapsize)
{
if(arr[left]>arr[index])
{
swap(arr,left,index);
}
}
else
{
while(left<heapsize)
{
if(left+1<heapsize)
{
int max = arr[left]>arr[left+1]?left:left+1;
int largest = arr[index]>arr[max]?index:max;
if(largest == index)
{
break;
}
else
{
swap(arr,index,largest);
index = largest;
}
}
else
{
if(arr[left]>arr[index])
{
swap(arr,left,index);
}
break;
}
left = 2*index+1;
}
}
}
int* MySort(int* arr, int arrLen, int* returnSize ) {
if(arrLen == 1)
{
*returnSize = arrLen;
return arr;
}
if(arrLen == 0)
{
*returnSize = arrLen;
return NULL;
}
heap(arr,0,arrLen);
int i;
for(i = arrLen-1;i>0;i--)
{
swap(arr, 0, i);
heapify(arr, 0, i);
}
i++;
swap(arr, 0, i);
*returnSize = arrLen;
return arr;
} 堆排序 时间复杂度为nlogn，空间复杂度为1；
发表于 2022-02-01 12:51:59
回复(0)
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
* 将给定数组排序
* @param arr int整型一维数组 待排序的数组
* @param arrLen int arr数组长度
* @return int整型一维数组
* @return int* returnSize 返回数组行数
*
* C语言声明定义全局变量请加上static，防止重复定义
*/
int patition(int* arr,int low,int high)
{
int temp=arr[low];
while(low<high)
{
while(arr[high]>=temp && low<high)
high--;
arr[low]=arr[high];
while(arr[low]<=temp && low<high)
low++;
arr[high]=arr[low];
}
arr[low]=temp;
return low;
}
void quicksort(int* arr ,int low, int high)
{
int pivotpos;
if(low<high)
{
pivotpos=patition(arr, low, high);
quicksort(arr, low, pivotpos-1);
quicksort(arr, pivotpos+1, high);
}
}
int* MySort(int* arr, int arrLen, int* returnSize ) {
// write code here
//快排
quicksort(arr,0,arrLen-1);
*returnSize=arrLen;
return arr;
}
发表于 2021-12-31 08:30:41
回复(0)
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
* 将给定数组排序
* @param arr int整型一维数组 待排序的数组
* @param arrLen int arr数组长度
* @return int整型一维数组
* @return int* returnSize 返回数组行数
*/
void Quick(int *arr, int Begin, int End)
{
if(Begin >= End) return;
int front = Begin, last = End, baseData = arr[Begin];
while(front < last)
{
while(arr[last] > baseData && last > front) last--;
if(arr[last] < baseData) arr[front] = arr[last];
while(arr[front] < baseData && last > front) front++;
if(arr[front] > baseData) arr[last] = arr[front];
}
arr[last] = baseData;
Quick(arr, Begin, last-1);
Quick(arr, last+1, End);
}
int* MySort(int* arr, int arrLen, int* returnSize ) {
// write code here
*returnSize = arrLen;
Quick(arr, 0, arrLen-1);
return arr;
}
发表于 2021-08-31 09:52:58
回复(0)
自己写的快排自测3ms通过，提交超时
int get_mid(int arr[], int L, int R)
{
int pivot = arr[L];
while (L < R)
{
while (arr[R] > pivot && L < R)
R--;
arr[L] = arr[R];
while (arr[L] < pivot && L < R)
L++;
arr[R] = arr[L];
}
arr[L] = pivot;
return L;
}
void quick_sort(int arr[], int L, int R)
{
if (L >= R) return;
quick_sort(arr, L, get_mid(arr, L, R));
quick_sort(arr, get_mid(arr, L, R) + 1, R);
}
int* MySort(int* arr, int arrLen, int* returnSize ) {
// write code here
quick_sort(arr, 0, arrLen - 1);
*returnSize = arrLen;
return arr;
} 用qsort通过 int cmp(const void * a, const void * b)
{
return (*(int*)a - *(int*)b);
}
int* MySort(int* arr, int arrLen, int* returnSize) {
// write code here
qsort(arr, arrLen, sizeof(int), cmp);
*returnSize = arrLen;
return arr;
}
发表于 2021-08-23 10:38:02
回复(0)
// C，快排，初学者
// 一开始没看到还要return *returnSize, 为什么不在题目里就说清😏
// 冒泡写的为啥自测能通过，但是提交会显示超时
int swap(int* ARR, int low, int high){
int temp;
temp = ARR[high];
ARR[high] = ARR[low];
ARR[low] = temp;
return 0;
}
int partition(int* ARR, int low, int high){
int pivotkey, m;
m = low + (high - low)/2;
if(ARR[low] > ARR[high]){
swap(ARR, low, high);
}
if(ARR[m] > ARR[high]){
swap(ARR, m, high);
}
if(ARR[low] < ARR[m]){
swap(ARR,low,m);
}
pivotkey = ARR[low];
while(low < high){
while(low < high && pivotkey <= ARR[high])
high --;
swap(ARR, low, high);
while(low < high && pivotkey >= ARR[low])
low ++;
swap(ARR, low, high);
}
return low;
}
void Qsort(int* ARR, int low, int high){
int pivot;
while(low < high){
pivot = partition(ARR, low, high);
Qsort(ARR, low, pivot-1);
low = pivot + 1;
}
}
int* MySort(int* arr, int arrLen, int* returnSize ) {
Qsort(arr, 0, arrLen-1);
*returnSize = arrLen;
return arr;
}
发表于 2021-08-15 22:08:00
回复(1)
//c语言简单直接，开始真搞不明白返回数组行数是啥，这题目真没说清楚，不知道是返回数组还是返回数组行数。
int* MySort(int* arr, int arrLen, int* returnSize ) {
int i = 0,j = 0;
//冒泡排序
for(i = 0;i<arrLen;i++){for(j = i;j<arrLen;j++){
if(arr[i]>arr[j]){
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
}
*returnSize = arrLen;
return arr;
}
发表于 2021-08-14 13:02:01
回复(0)
问题信息
难度：
19条回答
997收藏
13158浏览
通过挑战的用户
查看代码-
2023-03-12 20:16:31
-
2023-03-10 16:50:57 -
2023-03-08 01:29:53 -
2023-02-26 20:40:50 -
2023-02-24 11:16:30
相关试题
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K2座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
